https://youtu.be/91E_W8JhSjs
42. Trapping Rain Water
给定 n 个非负整数表示海拔图，其中每个条形的宽度为 1，
计算下雨后它可以捕获多少水。
https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png
Topics: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack
简单版解法 就是每个点都找到各自的 左边最高峰值 跟 右边最高峰值 就好
剩下就水到渠成 每个点只要比各自的左右峰值低 就能储水
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
maxLeft, maxRight = [0] * n, [0] * n
for i in range(1, n):
maxLeft[i] = max(height[i-1], maxLeft[i-1])
for i in range(n-2, -1, -1):
maxRight[i] = max(height[i+1], maxRight[i+1])
ans = 0
for i in range(n):
waterLevel = min(maxLeft[i], maxRight[i])
if waterLevel >= height[i]:
ans += waterLevel - height[i]
return ans
难点在于 space O(1) 吧 就不能每个点建立 maxLeft array 跟 maxRight array
而是只能用一个 maxLeft 和 maxRight int 当变量
这里用 two pointers
左指标跟右指标
然后考虑到maxLeft和maxRight的高低来决定谁是critical factor (水往低处流)
再去决定要计算移动 左指标和maxLeft 还是 右指标和maxRight
class Solution:
def trap(self, height: List[int]) -> int:
if len(height) <= 2: return 0
n = len(height)
maxLeft, maxRight = height[0], height[n-1]
left, right = 1, n - 2
ans = 0
while left <= right:
if maxLeft < maxRight:
if height[left] > maxLeft:
maxLeft = height[left]
else:
ans += maxLeft - height[left]
left += 1
else:
if height[right] > maxRight:
maxRight = height[right]
else:
ans += maxRight - height[right]
right -= 1
return ans
这题HARD的难点大概在于进阶解法 这要我自己想大概会想到睡着:(
然后stack的解法我也懒得读了 这交给以后的我解决就好