题目内容

给定 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

提示

1、n == height.length
2、0 <= n <= 3 * 10^4
3、0 <= height[i] <= 10^5

题解

本题的核心解题思想是单调栈的运用。

单调栈，即每次入栈的元素呈现单调的特点，要么是单调升，要么是单调减。

在本题中，我们可以考虑每个位置左边和右边的第一个比自身高的矩形条，以及三个矩形条构成的 U 型，这里就相当于对水的面积按行进行拆解。这里可以考虑维护一个严格单调递减的单调栈，具体操作如下：

当进栈的矩形高度小于等于栈顶举行高度时，将当前矩形压入栈中。当进栈的矩形高度大于当前栈顶矩形高度时，分别计算形成的U型中横向切割的每个小方形的长和宽，计算横向区域的方形凹槽面积，每次计算完就弹出当前栈顶元素，直到栈中的某个矩形的高度大于当前矩形高度，然后将该矩形压入栈中，继续刚才的判断，直到全部面积计算完毕。

代码

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> stk;
        int res = 0;
        for (int i = 0; i < height.size(); i ++ ) {
            int last = 0;//记录上一个柱子的高度
            while (stk.size() && height[stk.top()] <= height[i]) {
              	//当栈非空，且栈顶元素小于等于当前矩形高度时形成了U型的区域，就要计算对应可接雨水的面积。
                res += (height[stk.top()] - last) * (i - stk.top() - 1);//这里计算类似1、2、3、4区域的面积
                last = height[stk.top()];
                stk.pop();
            }

            if (stk.size()) res += (i - stk.top() - 1) * (height[i] - last);//计算类似5区域的面积
            stk.push(i);
        }

        return res;
    }
};