z

栈排序

单调栈

单调栈是一种和单调队列类似的数据结构。单调队列主要用于解决滑动窗口问题，单调栈则主要用于 [公式] 解决NGE问题（Next Greater Element），也就是，对序列中每个元素，找到下一个比它大的元素。（当然，“下一个”可以换成“上一个”，“比它大”也可以换成“比他小”，原理不变。)

这比单调队列还简单一点。我们维护一个栈，表示“待确定NGE的元素”，然后遍历序列。当我们碰上一个新元素，我们知道，越靠近栈顶的元素离新元素位置越近。所以不断比较新元素与栈顶，如果新元素比栈顶大，则可断定新元素就是栈顶的NGE，于是弹出栈顶并继续比较。直到新元素不比栈顶大，再将新元素压入栈。显然，这样形成的栈是单调递减的。

42. 接雨水

image-20220403161920414

方法一：按行求

依次遍历每一行，思路比较简单，理解容易除了超时之外并无明显缺点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int trap(vector<int>& height) {
        int maxh = 0;
        for(auto&h : height)maxh = max(maxh,h);
        int len = height.size();

        int water = 0;
        for(int h = maxh;h >= 0;h--){
            int left = -1;
            for(int i = 0;i < len;i++){      
                if(height[i] >= h){
                    if(left != -1)water += (i - left - 1);
                    left = i;
                }
            }
        }
        return water;
    }
};

方法二：按列求

image-20220403163938090

遍历每一列，然后分别求出这一列两边最高的墙。找出较矮的一端，和当前列的高度比较，如果当前列高度更低说明可以装下雨水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        vector<int>max_left(len,0);vector<int>max_right(len,0);
        for(int i = 1;i < len;i++){
            max_left[i] = max(max_left[i-1],height[i-1]);
        }
        for(int i = len - 2;i >= 0;i--){
            max_right[i] = max(max_right[i+1],height[i+1]);
        }
        
        int water = 0;
        for(int i = 1;i < len - 1;i++){
            int minl = min(max_left[i],max_right[i]);
            if(height[i] < minl)water += minl - height[i];
        }
        return water;
    }
};

方法三：按面积求

数学方法，这个方法放到高中卷子里我兴许能想的出来

image-20220403164128618

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        long long red = 0;
        int maxl = 0;
        for(int i = 0;i < len;i++){
            maxl = max(maxl,height[i]);
            red += maxl;
        }
        long long blue = 0;long long sum = 0;
        maxl = 0;
        for(int j = len - 1;j >= 0;j--){
            maxl = max(maxl,height[j]);
            blue += maxl;
            sum += height[j];
        }

        return red + blue - maxl*len - sum;
    }
};

方法四：单调栈

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
class Solution {
public:
    int trap(vector<int>& height) {
        stack<int>s;

        int size = height.size();
        int water = 0;
        for(int right = 0;right < size;right++){
            while(!s.empty() && height[right] > height[s.top()]){//碰到更高的，可以出栈了
                int bottom = s.top();
                s.pop();//pop出一个，这个是作为底的
                if(s.empty())break;

                int left = s.top();//左边界
                int leftHeight = height[left];
                int rightHeight = height[right];
                int bottomHeight = height[bottom];

                water += (right - left - 1)*(min(leftHeight,rightHeight) - bottomHeight);
            }
            s.push(right);
        }
        return water;
    }   
};

84. 柱状图中最大的矩形

image-20220407153741971

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

85. 最大矩形

image-20220407163238628

image-20220407163538364

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
38
39
40
41
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int size = heights.size() + 2;
        vector<int>he(size,0);
        for(int i = 1;i < size - 1;i++)he[i] = heights[i-1];
        
        stack<int>st;
        st.push(0);
        int maxa = 0;
        for(int i = 1;i < size;i++){
            while(he[st.top()] > he[i]){
                int curh = he[st.top()];
                st.pop();
                int left = st.top(); 
                maxa = max(maxa,(i - left - 1) * curh);
            }
            st.push(i);
        }
        return maxa;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>>heights(m,vector<int>(n,0));
        for(int i = 0;i < n;i++)
            if(matrix[0][i] == '1')heights[0][i] = 1;
        
        for(int i = 1;i < m;i++){
            for(int j = 0;j < n;j++){
                if(matrix[i][j] == '1'&&matrix[i-1][j] == '1')
                    heights[i][j] = heights[i-1][j] + 1;
                else if(matrix[i][j] == '1')
                    heights[i][j] = 1;
                else heights[i][j] = 0;
            }
        }
        int maxa = 0;
        for(int i = 0;i < m;i++)maxa = max(maxa,largestRectangleArea(heights[i]));
        return maxa;
    }
};

739. 每日温度

image-20220407155359312

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int size = temperatures.size();

        stack<int>s;
        vector<int>results(size,0);
        for(int right = 0;right < size;right++){
            int cnt = 0;
            while(!s.empty() && temperatures[s.top()] < temperatures[right]){
                results[s.top()] = right - s.top();
                s.pop();
                if(s.empty())break;
            }
            s.push(right);
        }
        return results;
    }
};