解析
11 Container With Most Water
- 面积公式 =
min(h[l], h[r]) * (r - l) - 判断
height[l]和height[r]的大小，如果height[l]小，l++，因为此时移动 r，并不会改变结果- 在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 -1 变短：
- 若向内 移动短板 ，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
- 若向内 移动长板 ，水槽的短板 min(h[i],h[j]) 不变或变小，因此下个水槽的面积 一定变小 。
- 在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 -1 变短：
# brute force
# - time: O(n2)
# - space: O(1)
# 双指针
# - time: O(n)
# - space: O(1)
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
max_water = 0
while l < r:
cur_water = (r - l) * min(height[l], height[r])
max_water = max(max_water, cur_water)
if height[l] < height[r]:
l += 1
else:
r -= 1
return max_water
ref
- https://www.youtube.com/watch?v=UuiTKBwPgAo
- https://leetcode.cn/problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
- https://neetcode.io/problems/max-water-container
42 Trapping Rain Water
- 一个格子能接的水，与该格子的高度、该格子左边中的最高的柱子的高度 和 该格子右边中的最高的柱子的高度 有关，即
min(leftMaxHeight, rightMaxHeight) - height[cur] - 因此，记下当前位置左边扫描过的的柱子的最高高度，同时，也记下当前位置扫描过的右边柱子的最高高度
- 如果当前扫描到的左边中的最高柱子的高度 低于 当前扫描到的右边中的最高柱子的高度，
l++，（因为这时候r–没有意义，因为左边柱子是瓶颈）- 算出当前柱子的盛水容量：
min(leftMaxHeight, rightMaxHeight) - height[cur] - 这时候，瓶颈在左边的最高柱子的高度，因而更新 当前扫描到的左边的最高柱子的高度
left_max = max(left_max, height[l])
- 算出当前柱子的盛水容量：
# brute force
# - time: O(n2)
# - space: O(1)
# 左右指针 - 写法 1（myself）
# - time: O(n)
# - space: O(1)
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
l, r = 0, len(height) - 1
maxLHeight, maxRHeight = height[l], height[r]
res = 0
while l < r:
if maxLHeight < maxRHeight:
l += 1
temp = min(maxLHeight, maxRHeight)
if temp > height[l]:
res += temp - height[l]
maxLHeight = max(height[l], maxLHeight)
else:
r -= 1
temp = min(maxRHeight, maxLHeight)
if temp > height[r]:
res += temp - height[r]
maxRHeight = max(height[r], maxRHeight)
return res
# 左右指针 - 写法 2（more elegent, Neetcode）
# - time: O(n)
# - space: O(1)
def trap(self, height: List[int]) -> int:
res = 0
left_max, right_max = height[0], height[-1]
l, r = 0, len(height) - 1
while l < r:
if left_max < right_max:
l += 1
diff = min(left_max, right_max) - height[l]
if diff > 0:
res += diff
left_max = max(left_max, height[l])
else:
r -= 1
diff = min(left_max, right_max) - height[r]
if diff > 0:
res += diff
right_max = max(right_max, height[r])
return res
ref