- 思路
- example
- 木桶效应，短板效应
- 每个格子左右两边最大值的短板(h), h - height[i] if this is
- 解法1：暴力法
- 复杂度. 时间：
)
, 空间: )
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
res = 0
for i in range(n):
leftMax = 0
for j in range(0, i):
leftMax = max(leftMax, height[j])
rightMax = 0
for j in range(i+1, n):
rightMax = max(rightMax, height[j])
if min(leftMax, rightMax) > height[i]:
res += min(leftMax, rightMax) - height[i]
return res
- 解法2：动规 (DP)
- 维护leftMax (-->)，rightMax数组 (<--)
- leftMax[i]: max of height[0], ..., height[i-1]
- rightMax[i]: max of height[i+1], ..., height[n-1]
- 复杂度. 时间：
)
, 空间:
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
leftMax = [0] * n
rightMax = [0] * n
for i in range(1, n):
leftMax[i] = max(leftMax[i-1], height[i-1])
for i in range(n-2, -1, -1):
rightMax[i] = max(rightMax[i+1], height[i+1])
res = 0
for i in range(n):
h = min(leftMax[i], rightMax[i])
if h > height[i]:
res += h - height[i]
return res
- 解法3：双指针: left, right. -->*<--
- 指针移动规则？
- 给定left, right (left <= right), 希望能够确定left 和 right其中一个位置的水位 （所能容纳的水量）。
- 可得到left之前（不包括left) 最大高度，以及right之后最大高度
- 假设height[left-1] < height[right+1], 则left这个位置的水位必然由leftMax[left]决定 (这个位置的储水不可能从右边界流出去）, 从而可以确定left这个位置的水位：max(0, leftMax[left] - height[left])
- 假设height[left -1] >= height[right+1], ....， 可以由rightMax[right]确定right这个位置的水位
- 上面的过程可以只维护当前的leftMax和rightMax 这两个数值。
- 复杂度. 时间：, 空间:
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n <= 2:
return 0
left, right = 1, n-2
leftMax, rightMax = height[0], height[n-1]
res = 0
while left <= right:
if height[left-1] < height[right+1]:
leftMax = max(leftMax, height[left-1])
res += max(0, leftMax - height[left])
left += 1
else:
rightMax = max(rightMax, height[right+1])
res += max(0, rightMax - height[right])
right -= 1
return res
- 解法四：优先队列 heapq (size = 2)
- que: 最小堆, 初始化存储第一个和最后一个 （高度，index)
- 从外往内遍历“填充”水位（因为水一定是从左右两个边界溢出），得用que，每次pop que 首位(heapq.heappop(que)) （左右边界中的最小高度---短板效应），然后判断该高度对应Index的邻居的水位。更新res, 更新新的边界入最小堆。
- 可以维护一个visited数组，确保不会重复访问。
- 复杂度. 时间：, 空间:
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n <= 2:
return 0
que = []
heapq.heappush(que, (height[0], 0))
heapq.heappush(que, (height[n-1], n-1))
visited = [False] * n
visited[0] = visited[n-1] = True
direction = [-1, 1]
res = 0
while que:
min_height, min_index = heapq.heappop(que)
for i in direction:
index = min_index + i
if index >= 0 and index <= n-1 and visited[index] == False:
min_height_new = max(min_height, height[index])
res += min_height_new - height[index]
visited[index] = True
heapq.heappush(que, (min_height_new, index))
return res
- 思路
- example
- 接雨水 高维版本
- 由外身内遍历边界 （水一定是从外边界溢出）
- 优先队列 （最小堆 heapq）
- directions方向向量: 方便考察最小边界周围点的水位
- visited数组避免重复访问
- 判断visited[x][y]时先检查x,y是否越界。
- 复杂度. 时间：
)
, 空间: )
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
m, n = len(heightMap), len(heightMap[0])
if m <= 2 or n <= 2:
return 0
res = 0
que = []
visited = [[False]*n for _ in range(m)]
directions = [(-1,0), (1,0), (0,-1), (0,1)]
for j in range(n):
heapq.heappush(que, (heightMap[0][j], (0,j)))
visited[0][j] = True
if m - 1 > 0:
heapq.heappush(que, (heightMap[m-1][j], (m-1,j)))
visited[m-1][j] = True
for i in range(1, m-1):
heapq.heappush(que, (heightMap[i][0], (i,0)))
visited[i][0] = True
if n -1 > 0:
heapq.heappush(que, (heightMap[i][n-1], (i,n-1)))
visited[i][n-1] = True
while que:
min_height, coordinate = heapq.heappop(que)
x0, y0 = coordinate[0], coordinate[1]
for direction in directions:
dx, dy = direction[0], direction[1]
x, y = x0 + dx, y0 + dy
if 0<=x<m and 0<=y<n and visited[x][y] == False:
min_height_new = max(min_height, heightMap[x][y])
res += min_height_new - heightMap[x][y]
visited[x][y] = True
heapq.heappush(que, (min_height_new, (x,y)))
return res
- 思路
- example
- 短板效应
- [left, right]: 储水量 = min(height[left], height[right]) * (right - left)
- 解法1：暴办法
- 复杂度. 时间：, 空间:
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
res = 0
for left in range(n):
for right in range(left+1, n):
res = max(res, min(height[left], height[right]) * (right - left))
return res
- 解法2：双指针， -->*<--
- left, right = 0, n-1
- 在更新完[left, right]结果后，考虑left += 1, 或者right -= 1
- 如果height[left] < height[right]: 考虑left += 1, 这样在宽度减小的情况下，min_height有可能增大；否则如果right-=1, min_height <= height[left]，不可能改进结果。
- 复杂度. 时间：, 空间:
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
left, right = 0, n-1
res = 0
while left < right:
res = max(res, min(height[left], height[right])*(right-left))
if height[left] < height[right]:
left += 1
else:
right -= 1
return res
