题目链接

给定 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 * 10^4
• 0 <= height[i] <= 10^5

解答

class Solution {
    public int trap(int[] height) {
        int res = 0;
        // 1.遍历数组，寻找数组中所有的局部最大值
        List<Integer> localMaxIndex = new LinkedList<>();        // 对于不低于左右相邻柱子的节点，称之为局部最大值
        if (height.length > 1 && height[0] > height[1]) localMaxIndex.add(0);
        for (int i = 1; i < height.length-1; i++)
            if (height[i] >= height[i-1] && height[i] >= height[i+1]) localMaxIndex.add(i);
        if (height.length > 1 && height[height.length-1] > height[height.length-2]) localMaxIndex.add(height.length-1);
        // 2.遍历局部最大值下标，寻找每个接雨水的区间
        int startPos = 0;
        // 遍历局部最大值，将每个局部最大值作为接雨水的开始区间位置
        while (startPos < localMaxIndex.size() - 1) {
            int currMax = startPos+1;
            // 将startPos更新为满足height[localMaxIndex.get(endPos)] >= height[localMaxIndex.get(startPos)]的最小的endPos。
            // 如果不存在，则更新为startPos后方，能使height[localMaxIndex.get(endPos)]最大的endPos值
            for (int endPos = currMax, startHeight = height[localMaxIndex.get(startPos)];
                 endPos < localMaxIndex.size(); endPos++) {
                if (height[localMaxIndex.get(endPos)] > height[localMaxIndex.get(currMax)]) currMax = endPos;
                if (height[localMaxIndex.get(endPos)] >= startHeight) break;
            }
            res += getTrap(localMaxIndex.get(startPos), localMaxIndex.get(currMax), height);
            startPos = currMax;
        }
        return res;
    }

    // 计算[startPos, endPos]中所接的雨水量
    private int getTrap(int startPos, int endPos, int[] height) {
        int effectiveHeight = Math.min(height[startPos], height[endPos]);
        int res = effectiveHeight*(endPos-startPos-1);
        for (int i = startPos+1; i < endPos; i++) res -= Math.min(height[i], effectiveHeight);
        return res;
    }
}