题目
解析
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 变短：
# solution 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/
42 Trapping Rain Water
- 一个格子能接的水，与该格子的高度、该格子左边中的最高的柱子的高度和该格子右边中的最高的柱子的高度有关，即
min(leftMaxHeight, rightMaxHeight) - height[cur] - 因此，记下当前位置左边中的最高柱子的高度，同时，也记下当前位置右边中的最高柱子的高度
- 如果当前扫描到的左边中的最高柱子的高度 低于 当前扫描到的右边中的最高柱子的高度，
l++，（因为这时候r–没有意义，因为左边柱子是瓶颈）- 算出当前柱子的盛水容量：
min(leftMaxHeight, rightMaxHeight) - height[cur] - 这时候，瓶颈在左边的最高柱子的高度，因而更新 当前扫描到的左边的最高柱子的高度
left_max = max(left_max, height[l])
- 算出当前柱子的盛水容量：
# solution 1 - 左右指针 - 写法 1（myself）
def trap(self, height: List[int]) -> int:
res = 0
l, r = 0, len(height) - 1
l_max, r_max = height[l], height[r]
while l < r:
if l_max <= r_max:
l += 1
cur_max = min(l_max, r_max)
if cur_max > height[l]:
res += cur_max - height[l]
l_max = max(l_max, height[l])
else:
r -= 1
cur_max = min(l_max, r_max)
if cur_max > height[r]:
res += cur_max - height[r]
r_max = max(r_max, height[r])
return res
# solution 2 - 左右指针 - 写法 2（more elegent, Neetcode）
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