LeetCode习题：接雨水

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

示例：

image

例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

提示：

• 1. n == height.length
• 2. 0 <= n <= 3 * 104
• 3. 0 <= height[i] <= 10^5

以下题解思路来源于LeetCode官方题解

解题语言： Swift

题解一：暴力求解

解题思路：直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。

func trap(_ height: [Int]) -> Int {
        if height.count <= 2 {
            return 0
        }
        var ans = 0
        let size = height.count
        for i in 1..<size - 1 {
            var max_left = 0, max_right = 0
            //Search the left part for max bar size
            for j in (0...i).reversed() {
                max_left = max(max_left, height[j])
            }
            // Search the right part for max bar size
            for k in i..<size {
                max_right = max(max_right, height[k])
            }
            ans += min(max_left, max_right) - height[I]
        }
        return ans
    }

复杂度分析：

时间复杂度：O(n^2)，数组中的每个元素都需要向左向右扫描。

空间复杂度: O(1)的额外空间。

题解二：动态规划

解题思路：对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。朴素的做法是对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组 height 的长度为 n，该做法需要对每个下标位置使用 O(n) 的时间向两边扫描并得到最大高度，因此总时间复杂度是 O(n^2)。上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。创建两个长度为 n 的数组 leftMax 和 rightMax。对于 0≤i<n，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度, rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。显然，leftMax[0]=height[0]，rightMax[n−1]=height[n−1]。两个数组的其余元素的计算如下：当 1≤i≤n−1 时，leftMax[i]=max(leftMax[i−1],height[i])；当 0≤i≤n−2 时，rightMax[i]=max(rightMax[i+1],height[i])。因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，反向遍历数组 height 得到数组 rightMax 的每个元素值。在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。遍历每个下标位置即可得到能接的雨水总量。

动态规划做法可以由下图体现。

image

class Solution {
    func trap(_ height: [Int]) -> Int {
        if height.count <= 2 {
            return 0
        }
        let size = height.count
        var leftMax = [Int](repeating: -1, count: size)
        leftMax[0] = height[0];
        for i in 1..<size {
            leftMax[i] = max(leftMax[i - 1], height[I]);
        }
        
        var rightMax = [Int](repeating: -1, count: size)
        rightMax[size - 1] = height[size - 1];
        for j in (0...size-2).reversed() {
            rightMax[j] = max(rightMax[j + 1], height[j]);
        }
        
        var ans = 0
        for i in 0..<size {
            ans += min(leftMax[i], rightMax[i]) - height[I];
        }
        return ans
    }
}

复杂度分析：

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

空间复杂度：O(n)，其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax 和 rightMax。

题目来源：LeetCode