16.接雨水

题目

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

思路

方法一：动态规划

对于下标i，下雨后水能到达的最大高度等于下标i两边的最大高度的最小值，
下标i处能接的雨水量等于下标i处的水能到达的最大高度减去height[i]。
朴素的做法是对于数组height中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。

上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。

创建两个长度为n的数组leftMax(存储每个位置左侧的最高柱子高度)和rightMax(存储每个位置右侧的最高柱子高度)。
对于leftMax[i]表示下标i及其左边的位置中，柱子的最大高度
rightMax[i]表示下标i及其右边的位置中，柱子的最大高度。
显然，leftMax[0]=height[0]，rightMax[n−1]=height[n−1]。
两个数组的其余元素的计算如下:
- 从左到右遍历，保障每次leftMax[i-1]是截止当前左边最大的。当1≤i≤n−1时，leftMax[i]=max(leftMax[i−1],height[i])；
- 从右到左遍历，保障每次rightMax[i+1]是截止当前右边最大的。当0≤i≤n−2时，rightMax[i]=max(rightMax[i+1],height[i])。
在得到数组leftMax和rightMax的每个元素值之后，对于下标i处能接的雨水量等于min(leftMax[i],rightMax[i])−height[i]。遍历累加每个下标位置即可得到能接的雨水总量。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 左右最小边界决定能存水的高度
            int minBound = Math.min(leftMax[i], rightMax[i]);
            // 当前柱子能存的水高度 = 最小边界 - 当前高度
            ans += minBound - height[i];
        }
        return ans;
    }
}

class Solution {
    fun trap(height: IntArray): Int {
        val length = height.size

        var rightHeight = IntArray(length) { 0 }
        var lefthHeight = IntArray(length) { 0 }

        var currentLeftHeight = 0
        var currentRightHeight = 0
        // [0,1,0,2,1,0,1,3,2,1,2,1]
        for (i in 1..<length) {
            currentLeftHeight = max(currentLeftHeight, height[i - 1])
            lefthHeight[i] = currentLeftHeight
        }
        for (i in length - 2 downTo 0) {
            currentRightHeight = max(currentRightHeight, height[i + 1])
            rightHeight[i] = currentRightHeight
        }

        var count = 0

        for (i in 0 ..< length) {
            var current = min(rightHeight[i], lefthHeight[i]) - height[i]
            if (current > 0) {
                count += current
            }
        }
        return count
    }
}

复杂度分析:

时间复杂度：O(n)，其中n是数组height的长度。计算数组leftMax和rightMax的元素值各需要遍历数组height一次，计算能接的雨水总量还需要遍历一次。
空间复杂度：O(n)，其中n是数组height的长度。需要创建两个长度为n的数组leftMax和rightMax。

方法二

动态规划的做法中，需要维护两个数组leftMax和rightMax，因此空间复杂度是O(n)。是否可以将空间复杂度降到O(1)？

注意到下标i处能接的雨水量由leftMax[i]和rightMax[i]中的最小值决定。

由于数组leftMax是从左往右计算，数组rightMax是从右往左计算，因此可以使用双指针和两个变量代替两个数组。
维护两个指针left和right，以及两个变量leftMax(左侧已扫描的最大高度)和rightMax(右侧已扫描的最大高度)，初始时left=0,right=length−1,leftMax是0坐标的值,rightMax是length - 1坐标的值。
所以这个时候，leftMax是左侧最大高度的最小值，rightMax是右侧最大高度的最小值
指针left向右移动，指针right向左移动，在移动指针的过程中维护两个变量leftMax和rightMax的值。

当两个指针没有相遇时，进行如下操作：

使用height[left]和height[right]的值去判断是不是超过当前的值来更新leftMax和rightMax的值
如果leftMax<rightMax，左边的高度是短板，能够接的数量由左边高度决定，下标left处能接的雨水量等于leftMax−height[left]，将下标left处能接的雨水量加到能接的雨水总量，然后将left加1（即向右移动一位）
如果leftMax≥rightMax，那右边的高度是短板，能够接的水量由右边的高度决定，下标right处能接的雨水量等于rightMax−height[right]，将下标right处能接的雨水量加到能接的雨水总量，然后将right减1（即向左移动一位）
当两个指针相遇时，就都循环完了，即可得到能接的雨水总量。

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            // 选择较小的边界进行计算
           // 如果height[left] < height[right]，说明右边存在一个较高的边界（至少是right指向的高度）能够保证左边有一个有效的边界（即leftMax）可以储水。
            // 因为此时，左边的最大值leftMax是影响当前位置储水的关键，右边已经有一个不小于height[left]的边界（right指针指向的高度更高）。
            if (height[left] < height[right]) {
                // 左侧是短板，计算左侧储水量
                ans += leftMax - height[left];
                left++;
            } else {
                // 右侧是短板，计算右侧储水量
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
}

class Solution {
    fun trap(height: IntArray): Int {
        var count = 0

        val length = height.size
        var leftMax = height[0]
        var rightMax = height[length - 1]

        var leftIndex = 0
        var rightIndex = length - 1

        while (leftIndex < rightIndex) {
            if (leftMax <= rightMax) {
                count += max(leftMax - height[leftIndex], 0)
                leftIndex ++
                leftMax = max(leftMax, height[leftIndex])
            } else {
                count += max(rightMax - height[rightIndex], 0)
                rightIndex --
                rightMax = max(rightMax, height[rightIndex])
            }
        }
        return count
    }
}

复杂度分析:

时间复杂度:O(n)，其中n是数组height的长度。两个指针的移动总次数不超过n。
空间复杂度：O(1)。只需要使用常数的额外空间。
下一篇

邮箱：charon.chui@gmail.com
Good Luck!