day49|42.接雨水，84.柱状图中最大的矩形

42.接雨水

42. 接雨水 - 力扣（LeetCode）

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), ans = 0;
        stack<int> stk; // 手动维持单调栈，height[栈底]>height[栈顶]
        for(int i = 0; i < n; i++){
            int curTop = 0;
            while(!stk.empty() && height[stk.top()] <= height[i]){ // 加等号是防止相同的块被多算
                curTop = stk.top();
                stk.pop();
                if(!stk.empty()){
                    ans += (min(height[i], height[stk.top()]) - height[curTop]) * (i - stk.top() - 1); 
                }
            }
            stk.push(i);
        }
        return ans;
    } 
};

84.柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（LeetCode）

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        int n = heights.size(), ans = 0;
        stack<int> stk;  // 单调栈，heights[top]最小。
        for(int i = 0; i < n; i++){
            int curTop = 0;
            if(!stk.empty() && heights[stk.top()] == heights[i]){
                stk.pop();
                stk.push(i);  // 取后面   1,0,0,1,0,0,1
                continue;
            }
            while(!stk.empty() && heights[stk.top()] > heights[i]){  // 处理相同块时要注意
                curTop = stk.top();
                stk.pop();
                if(!stk.empty()){
                    ans = max(ans, (i - stk.top() - 1) * heights[curTop]);  // 以curTop为高的最大矩形
                }else{
                    ans = max(ans, i * heights[curTop]);
                }
            }   
            stk.push(i);
        }
        heights.pop_back();
        return ans;
    }
};

原文地址：https://blog.csdn.net/bindloy/article/details/140691312

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！