leetcode_day51

今日内容：

• 42. 接雨水 hard
• 84. 柱状图中最大的矩形 hard

42. 接雨水

题目：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

alt text

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

思路：

由木桶效应，水量由最短板决定，所以这里每一格的水量由左右两边最低的柱子决定，同时还要减去自己的高度。

那么就需要知道每一格左右两边的最高柱子，取其小作为水面高度，减去自身高度即为水深。

求左右两边的某最值，且为一维数组，就尝试用单调栈。

个人版：设左右两个栈，底到顶递增，由于左右两柱子不接水，从左到右遍历就左栈只入栈最左柱，右栈入栈[2:size - 1]，然后取两个栈顶中较小的。

计算完当前柱，要把当前柱入栈左栈，注意维护大小关系，若当前高度等于右栈的栈底最大值，则要移除右栈的栈底。故数据结构用deque

carl版：一个栈就够了，栈规则相同递增，如果遇到比栈顶大的，就逐个出栈计算值，直到栈空或遇到左高柱。一次取当前柱(右柱)，栈顶柱(凹陷)，栈次顶柱(左柱)，算中间凹陷的水量。

• 另有双指针版，两个数组left、right分别表示heights[i]对应的左边最大值left[i]和右边最大值right[i]，初始先从左到右遍历得到left，从右到左遍历得到right，再遍历整个计算水量。需要注意维护和初始化

代码

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() == 1) return 0;
        deque<int> left, right;
        left.push_front(height[0]);
        for(int i = 2;i < height.size();i++) {
            while(!right.empty() && height[i] > right.back()) {
                right.pop_back();
            }
            right.push_back(height[i]);
        }
        int ans = 0;
        for(int i = 1;i < height.size() - 1;i++) {
            int l = left.front(), r = right.front();
            if(min(l, r) - height[i] > 0) ans += min(l, r) - height[i];
            while(!left.empty() && left.back() < height[i]) {
                left.pop_back();
            }
            left.push_back(height[i]);
            if(i > 1 && right.front() == height[i]) right.pop_front();
        }
        return ans;
    }
};

carl版：

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0; // 可以不加
        stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度
        st.push(0);
        int sum = 0;
        for (int i = 1; i < height.size(); i++) {
            if (height[i] < height[st.top()]) {     // 情况一
                st.push(i);
            } if (height[i] == height[st.top()]) {  // 情况二
                st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。
                st.push(i);
            } else {                                // 情况三
                while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while
                    int mid = st.top();
                    st.pop();
                    if (!st.empty()) {
                        int h = min(height[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1; // 注意减一，只求中间宽度
                        sum += h * w;
                    }
                }
                st.push(i);
            }
        }
        return sum;
    }
};

# 84. 柱状图中最大的矩形

题目：

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

alt text

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

思路：

要么追求高度，要么追求宽度，都得兼顾，每次计算都算包含当前柱的矩形面积，需要知道左边不小于自己的最远的柱子，右边不小于自己的最远的柱子。

单调栈：不小于自己的最远柱，那么入栈不小于的，碰到比栈顶小的就说明不能再贪宽度了，否则就损失高度了，此时逐个出栈计算面积，刚开始高窄，后面矮宽，总有一个最大，直到栈空或比栈顶大。

双指针：

左右都遍历，与上面相同的顺序，只是每次循环内要再循环一次往找过的地方针对当前柱找不小于的最远柱，可以利用已经计算的left和right数组跳跃寻找。

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size() == 0) {
            return heights[0];
        }
        stack<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        st.push(0);
        int ans = 0;
        for(int i = 1;i < heights.size();i++) {
            while(!st.empty() && heights[st.top()] > heights[i]) {
                int mid = st.top();
                st.pop();
                if(!st.empty()) {
                    int right = i;
                    int left = st.top();
                    ans = max(ans, heights[mid] * (right - left - 1));
                }
            }
            st.push(i);
        }
        return ans;
    }
};

双指针：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        //左边大于自己的最远的，右边大于自己的最远的
        vector<int> left(heights.size(), -1);
        vector<int> right(heights.size(), heights.size());
        
        for(int i = 1;i < heights.size();i++) {
            int t = i - 1;
            while(t >= 0 && heights[t] >= heights[i]) t = left[t];
            left[i] = t;
        }
        for(int i = heights.size() - 2;i >= 0;i--) {
            int t = i + 1;
            while(t < heights.size() && heights[t] >= heights[i]) t = right[t];
            right[i] = t;
        }
        int ans = 0;
        for(int i = 0;i < heights.size();i++) {
            ans = max(ans, heights[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }
};

小结

单调栈适用于找一维数组上，每个元素左右最大最小之类的最值。

设定好规则后，只需入栈符合规则的，遇到违背规则的就逐个出栈处理，直到符合规则，注意初始化以使栈内元素都能得到处理，防止漏解。