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 * 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;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容