单调栈
84.柱状图中最大的矩形
https://leetcode.cn/problems/largest-rectangle-in-histogram/
单调栈题目思维套路:
- 确定递增递减一关键在于考虑“前面不能影响到后面”的条件
- 本题中若h[i-1]> h[i], 则h[i- 1]这个高度就无法影响到更后面，自然可以单独计算了
单调栈题目代码套路:
- for 每个元素
while (栈顶与新元素不满足单调性) {弹栈,更新答案,累加“宽度”}
入栈
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; };
单调队列
239.滑动窗口最大值
https://leetcode.cn/problems/sliding-window-maximum/
单调队列题目思维套路:
- 单调队列维护的是一个候选集合，前面的比较旧，后面的比较新(时间有单调性)
- 候选项的某个属性也具有单调性
- 确定递增递减的方法一考 虑任意两个候选项j1
排除冗余的关键:若j1比j2差，j1 的生命周期还比j2短,那j1就没卵用了
单调队列题目代码套路:
- for每个元素
(1) while (队头过期)队头出队
(2)取队头为最佳选项，计算答案
(3) while (队尾与新元素不满足单调性)队尾出队
(3)新元素入队
(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; };
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; } };
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; };
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; };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
