42.接雨水问题

Trapping Rain Water

Hard

8726 133 Add to List Share

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

image

<pre style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 13px; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgb(247, 249, 250); padding: 10px 15px; color: rgb(38, 50, 56); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
</pre>

Example 2:

Constraints:

n == height.length
0 <= n <= 3 * 10<sup>4</sup>
0 <= height[i] <= 10<sup>5</sup>

这道题解决的关键在于把这个问题抽象成什么，对于任意一个位置i，l[i] 表示从当前位置到列表左端的最大值，r[i] 表示从当前位置到列表右端的最大值 min (l[i],r[i]) - height[i] , 表示当前位置可以积累的雨水

solution1## 动态规划

  class Solution:
    def trap(self, height: List[int]) -> int:
        length = len(height)
        # height[:i] 中最大的元素
        leftMax = [0]*length
        # height[i+1:] 中最大的元素
        rightMax = [0]*length
        for i in range(length):
            if i == 0: leftMax[i] = height[i]
            else:
                leftMax[i] = max(leftMax[i-1],height[i])
        for j in range(length-1,0,-1):
            if j == length-1 : rightMax[j] = height[j]
            else:
                rightMax[j] = max(height[j],rightMax[j+1])
        ans = 0
        for i in range(1,length-1):
            diff = min(leftMax[i-1],rightMax[i+1])
            if  diff > height[i]:
                ans += diff - height[i]
                
        return ans

solution 2## 两个指针
在height列表的左端和右端各定义一个指针，定义左边最大值为left_max, 右边最大值为right_max. 如果左边最大值小于右边最大值，ans += left_max - height[left]，指针左移，反之同理。直到两个指针相碰结束。

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0
        ans = 0
        left = 0
        right = len(height) -1
        left_max = height[left]
        right_max = height[right]
        while left < right:
            if left_max < right_max:
                ans += left_max - height[left]
                left += 1
                left_max = max(left_max,height[left])
            else:
                ans += right_max - height[right]
                right -= 1
                right_max = max(right_max, height[right])
        return ans

42.接雨水问题

solution1## 动态规划

solution 2## 两个指针