1、什么是单调栈？

顾名思义，单调栈就是栈内元素具有单调性。分为单调递增栈和单调递减栈。

  1. 单调递增栈就是从栈底到栈顶是从大到小。
  2. 单调递减栈就是从栈底到栈顶是从小到大。

即递增递减根据出栈顺序确定，而不是在栈中数据的顺序。

2、单调栈的适用问题

通过使用单调栈，可以找到从左/右遍历第一个比它小/大的元素的位置。也就是说在队列或数组中，我们需要通过比较前后元素的大小关系来解决问题时我们通常使用单调栈。

3、单调栈的算法流程

（单调递增栈）遍历数组，维护一个栈，对于当前元素的数值如果小于栈顶元素的数值，则将其压入栈顶；否则就一直弹出栈顶，直到栈空或者当前元素的数值小于栈顶元素的数值。

实例 : nums = [7,3,4,9,1,0,8,6,2]

  1. 枚举第一个元素7。此时栈空，入栈。栈内元素：7。
  2. 枚举第二个元素3。此时栈顶元素7 > 3，则入栈。栈内元素：7，3。
  3. 枚举第三个元素4。此时栈顶元素3 < 4，则栈顶元素出栈。此时栈顶元素7 > 4，则入栈。栈内元素：7，4。
  4. 枚举第四个元素9。此时栈顶元素4 < 9，则栈顶元素出栈。此时栈顶元素7 < 9，则栈顶元素出栈。此时栈空，入栈。栈内元素：9。
  5. 枚举第五个元素1。此时栈顶元素9 > 1，则入栈。栈内元素：9，1。
  6. 枚举第六个元素0。此时栈顶元素1 > 0，则入栈。栈内元素：9，1，0。
  7. 枚举第七个元素8。此时栈顶元素0 < 8，则栈顶元素出栈。此时栈顶元素1 < 8，则栈顶元素出栈。此时栈顶元素9 > 8，则入栈。栈内元素：9，8。
  8. 枚举第八个元素6。此时栈顶元素8 > 6，则入栈。栈内元素：9，8，6。
  9. 枚举第九个元素2。此时栈顶元素6 > 2，则入栈。栈内元素：9，8，6，2。

4、单调栈的伪代码

1
2
3
4
5
6
7
//单调递增栈
stack<int> st;
for(遍历数组){
	while(栈不空 && 栈顶元素 <= 当前元素) st.pop();
	更新结果;
	当前元素入栈;
}

5、例题

A.每日温度

单调递增栈，从后往前遍历数组，如果栈顶元素值小于等于当前元素值，则栈顶元素出队。直到栈空或者栈顶元素值大于当前元素值。更新结果：如果栈空，结果为0，如果不为空，结果为栈顶元素位置减去当前元素位置 。然后将当前元素入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int> ans(n);
        stack<int> st;
        for(int i = n - 1;i >= 0;i--){
            while(!st.empty() && T[st.top()] <= T[i])   st.pop();
            ans[i] = st.empty() ? 0 : st.top() - i;
            st.push(i);
        }
        return ans;
    }
};

B.柱状图中最大的矩形

单调递减栈。枚举高度，对于每个高度找到前一个比它小的位置和后一个比它小的位置，这两个位置之间的所有柱子高度都小于当前元素。用两次单调递增栈分别求出左侧和右侧最近小于其高度的柱子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n),right(n);
        stack<int> st;
        for(int i = 0;i < n;i++){
            while(!st.empty() && heights[st.top()] >= heights[i])    st.pop();
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
        while(!st.empty())  st.pop();
        for(int i = n-1;i >= 0;i--){
            while(!st.empty() && heights[st.top()] >= heights[i])    st.pop();
            right[i] = st.empty() ? n : st.top();
            st.push(i);
        }
        int ans = 0;
        for(int i = 0;i < n;i++){
            ans = max(ans,(right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};

6、总结

单调栈的时间复杂度是O(n)，空间复杂度是O(n)。可以用于求出左右两侧大于或者小于此元素的第一个元素。