用python写leetcode接雨水 带注释
时间: 2023-09-10 13:04:47 浏览: 85
### 回答1:
我可以给你一个用Python写LeetCode接雨水带注释的示例:def trap(height):
"""
:type height: List[int]
:rtype: int
"""
# 一个指针从左到右扫描数组,另一个指针从右到左扫描数组
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
# 结果
res = 0
while left < right:
if height[left] < height[right]:
# 如果左边的高度小于右边,则更新左边最大值
if height[left] >= left_max:
left_max = height[left]
else:
# 如果左边的高度小于左边最大值,则可以获得积水
res += left_max - height[left]
left += 1
else:
# 如果右边的高度小于左边,则更新右边最大值
if height[right] >= right_max:
right_max = height[right]
else:
# 如果右边的高度小于右边最大值,则可以获得积水
res += right_max - height[right]
right -= 1
return res
### 回答2:
以下是用Python编写LeetCode题目“接雨水”的代码,附有详细注释:
```python
def trap(height):
if not height:
return 0
n = len(height)
left_max = [0] * n # 创建一个与height长度相同的数组作为左侧最大值的容器
right_max = [0] * n # 创建一个与height长度相同的数组作为右侧最大值的容器
# 计算每个位置左侧的最大值并保存在left_max数组中
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(height[i], left_max[i-1])
# 计算每个位置右侧的最大值并保存在right_max数组中
right_max[n-1] = height[n-1]
for i in range(n-2, -1, -1):
right_max[i] = max(height[i], right_max[i+1])
total_water = 0 # 初始化总接雨水量为0
# 遍历每个位置,计算该位置能接的雨水量并累加到总接雨水量中
for i in range(1, n-1):
water_height = min(left_max[i], right_max[i]) - height[i] # 计算当前位置的接雨水量
if water_height > 0:
total_water += water_height
return total_water
```
这段代码的主要思路是,对于每个柱子,我们需要知道它左侧的最大值和右侧的最大值,然后取两者中较小的值减去当前柱子的高度,即为该位置能接的雨水量。最后将所有位置的雨水量累加起来,得到总的接雨水量。
为了方便计算左侧和右侧的最大值,我们分别创建了两个数组`left_max`和`right_max`,分别保存每个位置左侧和右侧的最大值。然后,我们再次遍历每个位置,计算当前位置能接的雨水量,并将其累加到总的接雨水量中。
这段代码的时间复杂度为O(n),其中n为输入列表height的长度。
### 回答3:
接雨水问题是一个经典的算法问题,在LeetCode上有多种解法。下面是使用Python编写的一种解法,并附有注释进行说明。
```python
class Solution:
def trap(self, height: List[int]) -> int:
if not height: # 如果输入为空,返回0
return 0
n = len(height)
left_max = [0] * n # 用于存储每个位置左侧的最大高度
right_max = [0] * n # 用于存储每个位置右侧的最大高度
left_max[0] = height[0] # 左侧的第一个柱子高度即为其自身的高度
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i]) # 计算每个位置左侧的最大高度
right_max[n-1] = height[n-1] # 右侧的最后一个柱子高度即为其自身的高度
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i]) # 计算每个位置右侧的最大高度
ans = 0
for i in range(1, n-1):
# 对于每个位置,接雨水的高度取决于左右两侧的最大高度中较小的一个减去当前位置的高度
# 如果该差值小于等于0,则说明该位置上不会有积水
ans += min(left_max[i], right_max[i]) - height[i]
return ans
```
这个算法的时间复杂度是O(n),其中n是输入列表height的长度。算法首先遍历两次输入列表,分别计算每个位置的左侧最大高度和右侧最大高度。然后再遍历一次输入列表,计算每个位置上的接雨水高度,并进行累加。算法使用了常量额外空间来存储两侧的最大高度,因此空间复杂度是O(n)。