吴良超的学习笔记

LeetCode解题报告(42)--柱状图的储水量

原题如下

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

从题目给出的图可以比较清楚知道,题目给出的数组中的每个数字代表一根柱子的高度,将数组中的数字全部表示为特定高度的柱子后,求这些柱子组成的容器能够容纳的水量。

解题思路:可以分别求出每根柱子的储水量,然后将每根柱子的储水量加起来即为总的储水量。而每根柱子的储水量可以通过下面方法求:找到这根柱子左边所有柱子中最高的那根,记为A;找到这根柱子右边所有柱子中最高的那根,记为B;min(A,B)-r即为这根柱子的储水量,r为这根柱子的高度。

实现代码如下:

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
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""

if len(height)==0:
return 0

leftMax = []
# leftMax Array
max = height[0]
for i in range(len(height)):
if height[i] > max :
max = height[i]
leftMax.append(max)

sum = 0
rightMax = height[len(height)-1]
for i in reversed(range(1,len(height)-1)):
miniHeight = min(leftMax[i-1],rightMax)
if miniHeight > height[i]:
sum += miniHeight - height[i]

if height[i] > rightMax:
rightMax = height[i]
return sum