首页 书籍 深入浅出程序设计竞赛(进阶篇) 常见优化技巧

单调栈是一种特殊的栈结构，用于解决一类特定的问题，比如寻找数组中元素的下一个更大元素或者下一个更小元素。它的特点是在栈中保持元素单调递增或单调递减。使用单调栈的目的主要是为了快速查找到某个元素左边或右边第一个比它大（或小）的元素。

# 单调栈的工作原理：

  1. 单调递增栈：当你需要处理找到每个元素右边第一个比它大的元素时，可以使用单调递增栈。处理过程中，如果当前元素比栈顶元素大，那么栈顶元素的右边第一个比它大的元素就是当前元素。

  2. 单调递减栈：当你需要处理找到每个元素右边第一个比它小的元素时，可以使用单调递减栈。处理过程中，如果当前元素比栈顶元素小，那么栈顶元素的右边第一个比它小的元素就是当前元素。

# 示例：

找到数组中每个元素右边第一个比它大的元素

这里给出一个使用单调栈解决问题的 C++ 示例代码：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1); // 初始化结果数组，假设所有元素右侧都没有更大的元素
    stack<int> s; // 使用栈来保存元素的索引
    
    for (int i = 0; i < n; ++i) {
        // 当栈不为空且当前元素大于栈顶元素所指向的值时
        while (!s.empty() && nums[i] > nums[s.top()]) {
            // 更新栈顶元素对应的结果
            result[s.top()] = nums[i];
            s.pop(); // 弹出栈顶元素
        }
        // 将当前元素的索引压入栈中
        s.push(i);
    }
    
    return result;
}
int main() {
    vector<int> nums = {2, 1, 2, 4, 3};
    vector<int> result = nextGreaterElement(nums);
    
    for (int i : result) {
        cout << i << " ";
    }
    cout << endl;
    
    return 0;
}
在这个例子中，我们维护了一个单调递减的栈。栈中存储的是数组元素的索引，而不是元素的值。这样做的目的是方便我们在找到一个元素的下一个更大元素时能够快速定位到该元素在结果数组中的位置，并更新它。当遍历到数组中的一个新元素时，我们检查栈顶元素代表的值是否小于当前元素的值。如果是，那么当前元素就是栈顶元素右边第一个比它大的元素，我们将结果记录下来，并从栈中移除栈顶元素。然后继续检查新的栈顶元素，直到栈为空或者栈顶元素代表的值大于等于当前元素的值。最后，将当前元素的索引压入栈中。


通过这种方式，我们能够在 O (n) 的时间复杂度内解决问题，其中 n 是数组的长度。这种方法比暴力求解的 O (n^2) 时间复杂度有显著的改进。


      

          
          
      

  


   


    

  
    
      
    
    更新于