[LeetCode]题解（python）：042-Trapping Rain Water

题目来源

https://leetcode.com/problems/trapping-rain-water/

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.

题意分析

Input: the height of the bars as list

Output: the volumn of the water the bars can save

Conditions:注意到因为bar的高度不一样，所以中间的bar可以容纳一定量的水，题意就是求容纳的水的大小

题目思路

注意到每一个bar所能容纳的水的量，就是其左右最高的bar中的较小值减去该bar的高度，所以先建立一个leftMostHigh的list记录每一个bar之前的最高bar值，然后从后往前遍历，一边更新右边最高的bar值，同时计算每一个bar所能容纳的水量

AC代码（Python）

 1 _author_ = "YE"
 2 # -*- coding:utf-8 -*-
 3 
 4 class Solution(object):
 5     def trap(self, height):
 6         """
 7         :type height: List[int]
 8         :rtype: int
 9         """
10         l = len(height)
11         leftMostHigh = [0 for i in range(len(height))]
12         leftmax = 0
13         for i in range(l):
14             leftMostHigh[i] = leftmax
15             if height[i] > leftmax:
16                 leftmax = height[i]
17 
18         rightmax = 0
19         sum = 0
20         for i in reversed(range(l)):
21             if min(rightmax, leftMostHigh[i]) > height[i]:
22                 sum = sum + min(rightmax, leftMostHigh[i]) - height[i]
23             if height[i] > rightmax:
24                 rightmax = height[i]
25 
26         return sum
27 
28 
29 height = [0,1,0,2,1,0,1,3,2,1,2,1]
30 s = Solution()
31 print(s.trap(height))