[已解决]接雨水代码题

Terence888

1. class Solution:
   
2.     def trap(self, height: List[int]) -> int:
   
3.         l, r = 0, len(height) - 1
   
4.         cap = 0
   
5.         leftCeil, rightCeil = 0, 0
   
6. 
   
7.         while l <= r:
   
8.             # 先更新 leftCeil, rightCeil
   
9.             leftCeil = max(leftCeil, height[l])
   
10.             rightCeil = max(rightCeil, height[r])
    
11. 
    
12.             if leftCeil < rightCeil:
    
13.                 cap += leftCeil - height[l] # 增加水量
    
14.                 l += 1  # 使 l 右移
    
15.             else:
    
16.                 cap += rightCeil - height[r] # 增加水量
    
17.                 r -= 1  # 使 r 左移
    
18. 
    
19.         return cap
    
20. 
    

复制代码

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

最佳答案

月排行榜 / 总排行榜

FishC

2024-10-21 11:59:23

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

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

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

1. from typing import List
   
2. 
   
3. class Solution:
   
4.     def trap(self, height: List[int]) -> int:
   
5.         l, r = 0, len(height) - 1
   
6.         cap = 0
   
7.         leftCeil, rightCeil = 0, 0
   
8. 
   
9.         while l < r:
   
10.             if height[l] < height[r]:
    
11.                 if height[l] >= leftCeil:
    
12.                     leftCeil = height[l]
    
13.                 else:
    
14.                     cap += leftCeil - height[l]
    
15.                 l += 1
    
16.             else:
    
17.                 if height[r] >= rightCeil:
    
18.                     rightCeil = height[r]
    
19.                 else:
    
20.                     cap += rightCeil - height[r]
    
21.                 r -= 1
    
22. 
    
23.         return cap

复制代码

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

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

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

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

跳转到最佳答案楼层

FishC

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

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

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

1. from typing import List
   
2. 
   
3. class Solution:
   
4.     def trap(self, height: List[int]) -> int:
   
5.         l, r = 0, len(height) - 1
   
6.         cap = 0
   
7.         leftCeil, rightCeil = 0, 0
   
8. 
   
9.         while l < r:
   
10.             if height[l] < height[r]:
    
11.                 if height[l] >= leftCeil:
    
12.                     leftCeil = height[l]
    
13.                 else:
    
14.                     cap += leftCeil - height[l]
    
15.                 l += 1
    
16.             else:
    
17.                 if height[r] >= rightCeil:
    
18.                     rightCeil = height[r]
    
19.                 else:
    
20.                     cap += rightCeil - height[r]
    
21.                 r -= 1
    
22. 
    
23.         return cap

复制代码

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

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

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

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