Leetcode 42. Trapping Rain Water

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Trapping Rain Water

2. Solution

解析:总的留存的雨水等于每个柱子上留存的雨水,而每个柱子上留存的雨水等于其左边最高柱子与右边最高柱子中较矮柱子的高度减去其高度。Version 1超时,Version 2是以空间换时间,Version 3是对Version 2的进一步优化。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
def trap(self, height):
length = len(height)
evalation_map = [0] * length
for i in range(length):
self.trap_rain(evalation_map, i, height)
return sum(evalation_map)
def trap_rain(self, evalation_map, index, height):
left = index
right = index
i = index
while i >= 0:
if height[i] > height[left]:
left = i
i -= 1
if left == index:
return
i = index
while i <= len(height) - 1:
if height[i] > height[right]:
right = i
i += 1
evalation_map[index] = min(height[left], height[right]) - height[index]
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def trap(self, height):
length = len(height)
evalation_map = [0] * length
left = [i for i in range(length)]
right = [i for i in range(length)]
max_index = 0
for i in range(length):
if height[i] >= height[max_index]:
max_index = i
else:
left[i] = max_index
max_index = length - 1
for i in range(length - 1, -1, -1):
if height[i] >= height[max_index]:
max_index = i
else:
right[i] = max_index
for i in range(length):
evalation_map[i] = min(height[left[i]], height[right[i]]) - height[i]
return sum(evalation_map)
  • Version 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def trap(self, height):
left = 0
right = len(height) - 1
result = 0
max_left_index = 0
max_right_index = len(height) - 1
while left < right:
if height[left] < height[right]:
if height[left] >= height[max_left_index]:
max_left_index = left
else:
result = result + height[max_left_index] - height[left]
left += 1
else:
if height[right] >= height[max_right_index]:
max_right_index = right
else:
result = result + height[max_right_index] - height[right]
right -= 1
return result

Reference

  1. https://leetcode.com/problems/trapping-rain-water/
如果有收获,可以请我喝杯咖啡!