代码随想录训练营day49|单调栈part2

接雨水

力扣题目链接

class Solution {
public:int trap(vector<int>& height) {int h = 0;int result = 0;stack<int> st;//存index// st.push(0);for(int i = 0; i < height.size(); i++){if(!st.empty() && height[st.top()] <= height[i]){while(!st.empty() && height[st.top()] < height[i]){h = height[st.top()];st.pop();if(!st.empty()){int w = i-st.top()-1;int h2 = min(height[st.top()], height[i])-h;result += h2 * w;}} }st.push(i);}return result;}
};

柱状图中最大的矩形

力扣题目链接

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;unordered_map<int, int> umap;stack<int> st;// 栈内元素递增for(int i = 0; i < heights.size(); i++){if(st.empty() || heights[st.top()] < heights[i]){st.push(i);}else{int j;// 遇到更小的元素时弹出，将入栈元素的index变为出栈的元素的，这里用覆盖heights来实现while(!st.empty() && heights[st.top()] >= heights[i]){j = st.top();// 判断局部矩阵result = max(result, (i-j) * heights[j]);heights[j] = heights[i];st.pop();}st.push(j);}}// 将递增栈的元素弹出，栈内元素满足到heights.size()处为矩形while(!st.empty()){int j = heights.size();result = max(result, heights[st.top()] * (j - st.top()));st.pop();}return result;}
};