42 接雨水

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

示例 1：

• 输入：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：

• 输入：height = [4,2,0,3,2,5]
• 输出：9

        本题可以用单调栈来求解，以往的单调栈问题中，都是找第一个比这个元素大的元素或者第一个比这个元素小的元素，而本题要找到左面的大元素和右面的大元素，右面的按照常规方法肯定好找，那么左面的呢？别忘了这是一个单调栈，栈里面的元素大小都是有规律的，栈顶的下一个元素就是左面的元素。用单调栈的方法解决接雨水问题属于横向求解，也就是每次解决一层而不是一列，用左右两个小高度的减去mid，然后再用左右两个的下标计算出宽度即可：

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        st.push(0);
        int sum = 0;
        for (int i = 1; i < height.size(); i++) {
            while (!st.empty() && height[i] > height[st.top()]) {
                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 。

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

 

        本题与上题类似，不过是要找左边第一个小的和右边第一个小的元素，同时要注意首位要先加一个0，以防原数组为递减序列时不返回结果，当然，上一题不需要（如果单调序列就接不到雨水了）。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.insert(heights.begin(), 0); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        st.push(0);
        int result = 0;
        for (int i = 1; i < heights.size(); i++) {
            while (heights[i] < heights[st.top()]) {
                int mid = st.top();
                st.pop();
                int w = i - st.top() - 1;
                int h = heights[mid];
                result = max(result, w * h);
            }
            st.push(i);
        }
        return result;
    }
};