接雨水代码题
class Solution:def trap(self, height: List) -> int:
l, r = 0, len(height) - 1
cap = 0
leftCeil, rightCeil = 0, 0
while l <= r:
# 先更新 leftCeil, rightCeil
leftCeil = max(leftCeil, height)
rightCeil = max(rightCeil, height)
if leftCeil < rightCeil:
cap += leftCeil - height # 增加水量
l += 1# 使 l 右移
else:
cap += rightCeil - height # 增加水量
r -= 1# 使 r 左移
return cap
为什么要遵循“谁小移动谁”的规则 接雨水（Trapping Rain Water）问题是一个常见的算法题，通常通过双指针方法来解决。我们需要计算柱子之间能够存储的雨水量。
首先，我们假设一个高度的列表 `height`。每个位置能够接收的水量，取决于当前位置的左边和右边的最高柱子高度。所以我们可以用两个指针和两个变量来分别记录左右边的最高高度。
以下是一个完整的 Python 解决方案：
from typing import List
class Solution:
def trap(self, height: List) -> int:
l, r = 0, len(height) - 1
cap = 0
leftCeil, rightCeil = 0, 0
while l < r:
if height < height:
if height >= leftCeil:
leftCeil = height
else:
cap += leftCeil - height
l += 1
else:
if height >= rightCeil:
rightCeil = height
else:
cap += rightCeil - height
r -= 1
return cap
解释：
1. 我们初始化两个指针 `l` 和 `r` 分别指向列表的开头和结尾。
2. `leftCeil` 和 `rightCeil` 分别记录当前左边和右边最大的高度。
3. 我们移动指针，比较两边的高度，根据较小边的高度来计算当前能够存储的水量，并不断更新最高高度和存储的雨水量。
4. 当 `l` 和 `r` 相遇时，循环结束，我们已经计算出所有能够存储的水量。
这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。
希望这个解答能帮到你！如果有其他问题，欢迎继续提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]