基础

每日温度

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 n=temperatures.size();
        vector<int> ans(n);
        
        stack<int> s;
        for(int i=0;i<n;i++){
            while(!s.empty()&&temperatures[s.top()]<temperatures[i]){ //栈中维护下标写法
                ans[s.top()]=i-s.top();
                s.pop();
            }
            s.push(i);
        }
 
        return ans;
    }
};

商品折扣后的最终价格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/***** 找后面第一个小于等于 *****/
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n=prices.size();
        vector<int> ans(n);
 
        stack<int> s;
        for(int i=0;i<n;i++){
            while(!s.empty()&&prices[s.top()]>=prices[i]){
                ans[s.top()]=prices[s.top()]-prices[i];
                s.pop();
            }
            s.push(i);
        }
        
        while(!s.empty()){
            ans[s.top()]=prices[s.top()];
            s.pop();
        }
        return ans;
    }
};

下一个更大元素 I

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
/***** 找后面第一个大 *****/
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans(nums1.size());
        unordered_map<int,int> hashmap;
        
        //处理nums2
        stack<int> s;
        for(int i=0;i<nums2.size();i++){
            while(!s.empty()&&nums2[s.top()]<nums2[i]){
                int temp=nums2[s.top()];
                hashmap[temp]=nums2[i];
                s.pop();
            }
            s.push(i);
        }
 
        for(int i=0;i<nums1.size();i++){
            int temp=nums1[i];
            if(hashmap[temp]) ans[i]=hashmap[temp];
            else ans[i]=-1;
        }
        return ans;
    }
};

下一个更大元素 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/***** 循环找后面第一个大 *****/
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n=nums.size();
        vector<int> ans(n,-1);
 
        stack<int> s;
        for(int i=0;i<2*n-1;i++){
            while(!s.empty()&&nums[s.top()]<nums[i%n]){
                ans[s.top()]=nums[i%n];
                s.pop();
            }
            s.push(i%n);
        }
        
        return ans;
    }
};

最大宽度坡

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 maxWidthRamp(vector<int>& nums) {
        stack<int> s;
        int n = nums.size();
        for (int i = 0;i < n;i++) {
            if (s.empty() || nums[s.top()] > nums[i]) {//要把第一个数据push
                s.push(i);
            }
        }
        int ans = 0;
        for (int i = n - 1;i >= 0;i--) {
            while (!s.empty() && nums[s.top()]<=nums[i]) {
                ans = max(ans,i - s.top());
                s.pop();
            }
        }
        return ans;
    }
};

车队

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 carFleet(int target, vector<int>& position, vector<int>& speed) {
        map<int,int> ps; //自动排序
        for(int i=0;i<position.size();i++){
            ps[position[i]]=speed[i];
        }

        stack<double> s;
        for(auto& [pos,spd]:ps){
            double time=double(target-pos)/spd;
            while(!s.empty()&&s.top()<=time){
                s.pop();
            }
            s.push(time);
        }
        return s.size();
    }
};

矩形面积（完结）

柱状图中最大的矩形

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
/***** 单调栈的其中一种写法---处理栈中元素 *****/
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n,-1), right(n,n); //左边第一个小的位置、右边第一个小的位置
        
        stack<int> s;
        for(int i=0;i<n;i++){ //处理右边
			while(!s.empty()&&heights[s.top()]>heights[i]){
				right[s.top()]=i;
				s.pop();
			}
			s.push(i);
		}
 
        s = stack<int> (); //清空栈
        for(int i=n-1;i>=0;i--){ //处理左边
			while(!s.empty()&&heights[s.top()]>heights[i]){
				left[s.top()]=i;
				s.pop();
			}
			s.push(i);
		}
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};

好子数组的最大分数

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
/***** 单调栈的另一种写法---处理当前元素 *****/
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> left(n,-1),right(n,n); //左边第一小的编号、右边第一小的编号
 
        stack<int> s;
        for(int i=0;i<n;i++){ //处理左边
            while(!s.empty()&&nums[s.top()]>=nums[i]) s.pop();
            if(!s.empty()) left[i]=s.top();
            s.push(i);
        }
 
        s=stack<int> ();
        for(int i=n-1;i>=0;i--){ //处理右边
            while(!s.empty()&&nums[s.top()]>=nums[i]) s.pop();
            if(!s.empty()) right[i]=s.top();
            s.push(i);
        }
        
        int ans=0;
        for(int i=0;i<n;i++){
            int h=nums[i],l=left[i],r=right[i];
            if(l<k&&r>k){ //多了一个区间判断
                ans=max(ans,h*(r-l-1));
            }
        }
        return ans;
    }   
};

最大矩形

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
42
43
44
45
46
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n=matrix.size(); //行数
        int m=matrix[0].size(); //列数
        vector<vector<int>> left(n,vector<int>(m,0));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]=='1'){
                    left[i][j]=(j==0?1:left[i][j-1]+1); //往左能够延申的最大长度
                }
            }
        }
        int ret=0;
 
        //对于每一列，使用基于柱状图求最大矩形的方法
        for(int j=0;j<m;j++){
            vector<int> up(n,0),down(n,0);
 
            stack<int> s;
            for(int i=0;i<n;i++){ 
                while(!s.empty()&&left[s.top()][j]>=left[i][j]){
                    s.pop();
                }
                up[i]=s.empty()?-1:s.top(); //上边第一个小于的编号
                s.push(i);
            }
            s=stack<int>();//清空栈
            for(int i=n-1;i>=0;i--){
                while(!s.empty()&&left[s.top()][j]>=left[i][j]){
                    s.pop();
                }
                down[i]=s.empty()?n:s.top(); //下边第一个小于的编号
                s.push(i);
            }
            
            for(int i=0;i<n;i++){
                int width=down[i]-up[i]-1;
                int area=width*left[i][j];
                ret=max(ret,area);
            }
        }
 
        return ret;
    }
};

统计全 1 子矩形

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
42
43
44
45
46
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n=mat.size();
        int m=mat[0].size();
        vector<int> height(m);
 
        /*单调栈求左右更小值(同时处理)*/
        auto calc=[&]()->int{
            vector<int> left(m,-1),right(m,m);
 
            stack<int> s;
            for(int i=0;i<m;i++){
                while(!s.empty()&&height[s.top()]>height[i]){
                    right[s.top()]=i;
                    s.pop();
                }
                if(!s.empty()){
                    left[i]=s.top();
                }
                s.push(i);
            }
 
            int ans=0;
            /* 计算结果时, 乘法原理 * 矩阵高度 */
            for(int i=0;i<m;i++){
                ans+=(right[i]-i)*(i-left[i])*height[i];
            }
            return ans;
        };
 
        int ans=0;
        for(int i=0;i<n;i++){ /* 遍历每一行的高度, 更新改行的高度值使用单调栈计算左侧更小值和右侧更小值,再计算每个小矩阵出现的次数*/
            for(int j=0;j<m;j++){
                if(mat[i][j]==0){
                    height[j]=0;
                }
                else{
                    height[j]++;
                }
            }
            ans+=calc();
        }
        return ans;
    }
};

接雨水

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
class Solution {
public:
    int trap(vector<int>& height) {
        int ans=0;
        int n=height.size();

        stack<int> s;
        for (int i=0;i<n;i++) {
            while (!s.empty() && height[s.top()]<height[i]) {
                int top = s.top();
                s.pop();
                if (s.empty()) {
                    break;
                }
                int left = s.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            s.push(i);
        }
        
        return ans;
    }
};
/***** 不能单纯找左边第一个大、右边第一个大 *****/
/*这种情况会多算
*   *
** **
** **
*****
*/

最小字典序

移掉 K 位数字