LeetCode 接雨水
题目来源:https://leetcode-cn.com/problems/trapping-rain-water/
今天在LeetCode上看到一道很有意思的题目:接雨水。
题目给出了一些柱子的高度,然后要求出这些柱子可以装的水有多少。
我想到的方法是从左往右遍历数组,记录当前的最高的柱子高度,只要遇到比最高柱子低的柱子,就假设这个柱子可以装下(最高柱子高度 - 较低柱子高度)的水。一遍遍历后,就会发现
图中绿色部分也会被记录下来,而实际上这部分是不能装水的,所以这时再从最后往前遍历数组,将多余的部分去掉,直到遇到最高的柱子为止。
python3 代码如下:
class Solution:
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
num = 0
h = 0
for i in range(len(height)):
if height[i] >= h:
h = height[i]
else:
num += h - height[i]
i = len(height)-1
small = 0
while i >= 0:
if h == height[i]:
break
if small < height[i]:
small = height[i]
num -= (h - small)
i -= 1
continue
if height[i] < h and height[i] > small:
num -= (h - height[i])
elif height[i] <= small:
num -= (h - small)
i -= 1
return num