单调栈

单调栈分为单调递增栈和单调递减栈

- 单调递增栈即栈内元素保持单调递增的栈
- 同理单调递减栈即栈内元素保持单调递减的栈

操作规则（下面都以单调递增栈为例）

  • 如果新的元素比栈顶元素大，就入栈

  • 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

  • 效果

    • 栈内的元素是递增的
    • 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素

    举个例子，配合下图，现在索引在 6 ，栈里是 1 5 6 。
    接下来新元素是 2 ，那么 6 需要出栈。
    当 6 出栈时，右边 2 代表是 6 右边第一个比 6 小的元素。

    • 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素

    当 6 出栈时，5 成为新的栈顶，那么 5 就是 6 左边第一个比 6 小的元素。

模板

1
2
3
4
5
6
7
8
9
10
stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
	while(!st.empty() && st.top() > nums[i])
	{
		st.pop();
	}
	st.push(nums[i]);
}

例题

84 柱状图中最大的矩形：

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        int ret = 0;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        stack<int> st;
        for(int i=0; i<heights.size(); i++){
            while(!st.empty() && heights[st.top()] > heights[i]){


85 最大矩形

https://leetcode.cn/problems/maximal-rectangle/description/

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix[0].size();
        int ans = 0;
        vector<int> heights(n, 0);
        for(int i=0; i<matrix.size(); i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j] == '0')
                    heights[j] = 0;
                else
                    heights[j]++;
            }
            ans = max(ans, maxRectangle(heights));
            heights.pop_back();
            heights.erase(heights.begin());
        }
        return ans;
    }
    int maxRectangle(vector<int>& heights){
        int ret = 0;
        heights.push_back(0);
        heights.insert(heights.begin(), 0);
        stack<int> st;
        for(int i=0; i<heights.size(); i++){
            while(!st.empty() && heights[st.top()] > heights[i]){
                int height = heights[st.top()];
                st.pop();
                int left = st.top() + 1;
                int right = i - 1;
                ret = max(ret, height * (right - left + 1));
            }
            st.push(i);
        }
        return ret;
    }
};