[已解决]接雨水代码题

Terence888

class Solution:
    def trap(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        cap = 0
        leftCeil, rightCeil = 0, 0

        while l <= r:
            # 先更新 leftCeil, rightCeil
            leftCeil = max(leftCeil, height[l])
            rightCeil = max(rightCeil, height[r])

            if leftCeil < rightCeil:
                cap += leftCeil - height[l] # 增加水量
                l += 1  # 使 l 右移
            else:
                cap += rightCeil - height[r] # 增加水量
                r -= 1  # 使 r 左移

        return cap

为什么要遵循“谁小移动谁”的规则

最佳答案

月排行榜 / 总排行榜

FishC

2024-10-21 11:59:23

接雨水（Trapping Rain Water）问题是一个常见的算法题，通常通过双指针方法来解决。我们需要计算柱子之间能够存储的雨水量。

首先，我们假设一个高度的列表 `height`。每个位置能够接收的水量，取决于当前位置的左边和右边的最高柱子高度。所以我们可以用两个指针和两个变量来分别记录左右边的最高高度。

以下是一个完整的 Python 解决方案：

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        cap = 0
        leftCeil, rightCeil = 0, 0

        while l < r:
            if height[l] < height[r]:
                if height[l] >= leftCeil:
                    leftCeil = height[l]
                else:
                    cap += leftCeil - height[l]
                l += 1
            else:
                if height[r] >= rightCeil:
                    rightCeil = height[r]
                else:
                    cap += rightCeil - height[r]
                r -= 1

        return cap

解释：
1. 我们初始化两个指针 `l` 和 `r` 分别指向列表的开头和结尾。
2. `leftCeil` 和 `rightCeil` 分别记录当前左边和右边最大的高度。
3. 我们移动指针，比较两边的高度，根据较小边的高度来计算当前能够存储的水量，并不断更新最高高度和存储的雨水量。
4. 当 `l` 和 `r` 相遇时，循环结束，我们已经计算出所有能够存储的水量。

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。

希望这个解答能帮到你！如果有其他问题，欢迎继续提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

接雨水（Trapping Rain Water）问题是一个常见的算法题，通常通过双指针方法来解决。我们需要计算柱子之间能够存储的雨水量。

首先，我们假设一个高度的列表 `height`。每个位置能够接收的水量，取决于当前位置的左边和右边的最高柱子高度。所以我们可以用两个指针和两个变量来分别记录左右边的最高高度。

以下是一个完整的 Python 解决方案：

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        cap = 0
        leftCeil, rightCeil = 0, 0

        while l < r:
            if height[l] < height[r]:
                if height[l] >= leftCeil:
                    leftCeil = height[l]
                else:
                    cap += leftCeil - height[l]
                l += 1
            else:
                if height[r] >= rightCeil:
                    rightCeil = height[r]
                else:
                    cap += rightCeil - height[r]
                r -= 1

        return cap

解释：
1. 我们初始化两个指针 `l` 和 `r` 分别指向列表的开头和结尾。
2. `leftCeil` 和 `rightCeil` 分别记录当前左边和右边最大的高度。
3. 我们移动指针，比较两边的高度，根据较小边的高度来计算当前能够存储的水量，并不断更新最高高度和存储的雨水量。
4. 当 `l` 和 `r` 相遇时，循环结束，我们已经计算出所有能够存储的水量。

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。

希望这个解答能帮到你！如果有其他问题，欢迎继续提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。