42. 接雨水

題目描述

給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。

image

上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個(gè)單位的雨水（藍(lán)色部分表示雨水）。 感謝 Marcos 貢獻(xiàn)此圖。

示例:

輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/trapping-rain-water

解題思路

• 方法1:
  • 計(jì)算每一列的雨水,最后累積和,其中雨水能達(dá)到的最高位置等于兩邊距離最近的高點(diǎn)的較小值減去當(dāng)前高度
• 方法2: 雙指針
  • 只要right_max[i] > left_max[i] ，積水高度將由 left_max 決定, 反之也成立
    所以我們可以認(rèn)為如果一端有更高的條形塊（例如右端），積水的高度依賴于當(dāng)前方向的高度（從左到右）。當(dāng)我們發(fā)現(xiàn)另一側(cè)（右側(cè)）的條形塊高度不是最高的，我們則開(kāi)始從相反的方向遍歷（從右到左）。
    我們必須在遍歷時(shí)維護(hù) left_max 和 right_max ，但是我們現(xiàn)在可以使用兩個(gè)指針交替進(jìn)行，實(shí)現(xiàn) 1 次遍歷即可完成。

代碼實(shí)現(xiàn)

• 方法1:

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height:
            return 0
        n = len(height)
        max_left = [0] * n
        max_right = [0] * n
        max_left[0] = height[0]
        max_right[-1] = height[-1]
        # 找位置i左邊最大值
        for i in range(1, n):
            max_left[i] = max(height[i], max_left[i-1])

        for i in range(n-2, -1, -1):
            max_right[i] = max(height[i], max_right[i+1])

        res = 0
        for i in range(n):
            res += min(max_left[i], max_right[i]) - height[i]
        return res

• 方法2:

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height: return 0
        left = 0
        right = len(height) - 1
        res = 0
        # 記錄左右兩邊最大值
        left_max = height[left]
        right_max = height[right]
        while left < right:
            if height[left] < height[right]:
                if left_max > height[left]:
                    res += left_max - height[left]
                else:
                    left_max = height[left]  # 更新 left_max
                left += 1
            else:
                if right_max > height[right]:
                    res += right_max - height[right]
                else:
                    right_max = height[right]  # 更新right_max
                right -= 1
        return res