leetcode 【 Trapping Rain Water 】python 实现

浏览数：16 / 时间：2015年06月11日

题目：

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!

代码：oj测试通过 Runtime: 91 ms

 1 class Solution:
 2     # @param A, a list of integers
 3     # @return an integer
 4     def trap(self, A):
 5         # special case
 6         if len(A)<3:
 7             return 0
 8         # left most & right most
 9         LENGTH=len(A)
10         left_most = [0 for i in range(LENGTH)]
11         right_most = [0 for i in range(LENGTH)]
12         curr_max = 0
13         for i in range(LENGTH):
14             if A[i] > curr_max:
15                 curr_max = A[i]
16             left_most[i] = curr_max
17         curr_max = 0
18         for i in range(LENGTH-1,-1,-1):
19             if A[i] > curr_max:
20                 curr_max = A[i]
21             right_most[i] = curr_max
22         # sum the trap
23         sum = 0
24         for i in range(LENGTH):
25             sum = sum + max(0,min(left_most[i],right_most[i])-A[i])
26         return sum