7.接雨水

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

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

题目思路

为什么使用单调栈？

因为如果柱子的高度是单调递减的，那么肯定存不下雨水，这样我们就将单调递减的柱子加入单调栈，这样如果一个高的柱子入栈，会导致栈顶元素出栈，我们就可以做出栈的时候进行水的容量计算「只有出栈的时候可能会存雨水」

• 遍历所有的柱子，对于每个柱子，将其信息存储在 right 中。
• 当栈不为空且栈顶元素的高度小于 right 的高度时，从栈中弹出元素 pop，并取栈顶元素作为 left。
• 计算 left 和 right 之间能存储雨水的空间，即根据宽度和高度的计算（宽度为 right.index - left.index - 1，高度为 Math.min(right.height, left.height) - pop.height），将计算结果累加到 sum 中。
• 最终得到的 sum 就是整个柱状图能存储的雨水总量。

题解代码

// 如果柱子的高度是单调递减的，那么肯定存不下雨水
// 如果出现了一个比之前柱子高的柱子，才有可能有空间能够存下雨水
// 使用一个单调 栈存放每个柱子的高度，当新来的柱子更高时，不满足单调栈的规则，需要弹出栈顶那些高度低的柱子的时候 计算雨水容量
// 此时涉及到三个变量，一个是刚加入的柱子，命名为right，一个是被弹出的柱子，命名为pop，还有一个是被弹出柱子左侧的柱子，命名left
// 水的容量 = (right的索引-left的索引-1) * min(right.height,left.height) - pop.height
// 因为对于每个柱子我们都需要用它的索引和高度两个状态，因此我们封装一个Data类来描述柱子
public int trap(int[] heights) {
    LinkedList<Data> stack = new LinkedList<>();
    int sum = 0;
    for (int i = 0; i < heights.length; i++) {
        Data right = new Data(heights[i], i); // 即将放入单调栈中的柱子
        while (!stack.isEmpty() && stack.peek().height < right.height) { // 查看单调栈顶元素是否小于准备入栈的元素
            Data pop = stack.pop(); // 从栈中pop出的柱子
            Data left = stack.peek(); // 栈中pop出柱子后的栈顶柱子就是原先pop柱子左侧的柱子
            // 如果左侧的柱子不为null
            if (left != null) {
                // 计算水的容量并累加
                int width = right.index - left.index - 1;
                int height = Math.min(right.height, left.height) - pop.height;
                sum += width * height;
            }
        }
        stack.push(right);
    }
    return sum;
}

static class Data {
    private int height; // 柱子高度
    private int index; // 柱子的索引

    public Data(int height, int index) {
        this.height = height;
        this.index = index;
    }
}