42. 接雨水

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

示例 1:

1653103354228

输入: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

算法思路:

采用双指针 p1、p2,分别从左右两边找最大高度 max1,max2,对于较小者的一方计算其能装的水量 【max1 (max2) — 当前位置下一高度 height[++p1] (height[–p2]),非负】,并累加起来,最后的和即最终答案。

代码实现:

class Solution {
    public int trap(int[] height) {
        int count = 0;
        int p1 = 0, p2 = height.length - 1;
        int max1 = height[p1], max2 = height[p2];
        // 两边分别找最大高度,把较小者能装的水量(较小者-其下一高度,非负)累加起来
        while (p2 > p1) {
            if (max1 < max2) {
                // 左边能装的水量
                count += Math.max(max1 - height[++p1], 0);
                max1 = Math.max(height[p1], max1);
            } else {
                // 右边能装的水量
                count += Math.max(max2 - height[--p2], 0);
                max2 = Math.max(height[p2], max2);
            }
        }
        return count;
    }
}

Q.E.D.


以无限为有限,以无法为有法