单调栈、单调队列

单调栈

84.柱状图中最大的矩形
https://leetcode.cn/problems/largest-rectangle-in-histogram/

单调栈题目思维套路:

• 确定递增递减一关键在于考虑“前面不能影响到后面”的条件
• 本题中若h[i-1]> h[i], 则h[i- 1]这个高度就无法影响到更后面，自然可以单独计算了

单调栈题目代码套路:

• for 每个元素

•  	while (栈顶与新元素不满足单调性) {弹栈,更新答案,累加“宽度”}
  1

•  	入栈
  1

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans=0;
        heights.push_back(0);
        for(int height: heights){
            int accumulateWidth = 0;
            while(!s.empty() && s.top().height >= height){
                accumulateWidth+=s.top().width;
                ans = max(ans,s.top().height * accumulateWidth);
                s.pop();
            }
            s.push({accumulateWidth+1,height});
        }

        return ans;
    }
private:
    struct Rect{
        int width;
        int height;
    };
    stack<Rect> s;    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

单调队列

239.滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum/

单调队列题目思维套路:

• 单调队列维护的是一个候选集合，前面的比较旧，后面的比较新(时间有单调性)
• 候选项的某个属性也具有单调性
• 确定递增递减的方法一考 虑任意两个候选项j1

排除冗余的关键:若j1比j2差，j1 的生命周期还比j2短,那j1就没卵用了

单调队列题目代码套路:

• for每个元素

•  (1) while (队头过期)队头出队
  1

•  (2)取队头为最佳选项，计算答案
  1

•  (3) while (队尾与新元素不满足单调性)队尾出队
  1

•  (3)新元素入队
  1

(2) (3)的顺序取决于:
i是不是候选项

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        for(int i=0;i<nums.size();i++){
            q.push({nums[i],i});
            if(i >= k-1){
                while(q.top().second <= i-k) q.pop();
                ans.push_back(q.top().first);
            }
        }
        return ans;
    }
private:
    priority_queue<pair<int,int>> q;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

42.接雨水
https://leetcode.cn/problems/trapping-rain-water/

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        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 trap(vector<int>& heights) {
        int ans =0;
        for(int height : heights){
            int accmulateWidth=0;
            while(!s.empty() && s.top().height <= height){
                
                int bottom = s.top().height;
                accmulateWidth += s.top().width;
                s.pop();
                if (s.empty()) continue;
                //int up = s.empty() ? 0 : min(height,s.top().height);
                int up = min(height,s.top().height);
                //if(!s.empty() && s.top().height < up) up = s.top().height;
                ans += accmulateWidth * (up - bottom);
            }
            s.push({accmulateWidth + 1,height});
        }
        return ans;
    }
private:
    struct Rect{
        int width;
        int height;
    };
    stack<Rect> s;    
};
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

class Solution {
public:
    int trap(vector<int>& heights) {
        int n=heights.size();
        preMax = vector<int>(n);
        sufMax = vector<int>(n);
        preMax[0] = heights[0];
        for(int i=1;i<n;i++) preMax[i] = max(preMax[i-1],heights[i]);
        sufMax[n-1] = heights[n-1];
        for(int i = n-2;i >= 0;i--) sufMax[i] = max(sufMax[i+1],heights[i]);
        int ans = 0;
        for(int i=1;i < n-1;i++)
        {
            int up = min(preMax[i-1],sufMax[i+1]);
            int bottom = heights[i];
            if(up > bottom) ans+=up - bottom;
        }
        return ans;
    }
private:
    vector<int> preMax;
    vector<int> sufMax;    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习