leetcode 【 Trapping Rain Water 】python 实现

题目：

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

 class Solution:

     # @param A, a list of integers

     # @return an integer

     def trap(self, A):

         # special case

         if len(A)<3:

             return 0

         # left most & right most

         LENGTH=len(A)

         left_most = [0 for i in range(LENGTH)]

         right_most = [0 for i in range(LENGTH)]

         curr_max = 0

         for i in range(LENGTH):

             if A[i] > curr_max:

                 curr_max = A[i]

             left_most[i] = curr_max

         curr_max = 0

         for i in range(LENGTH-1,-1,-1):

             if A[i] > curr_max:

                 curr_max = A[i]

             right_most[i] = curr_max

         # sum the trap

         sum = 0

         for i in range(LENGTH):

             sum = sum + max(0,min(left_most[i],right_most[i])-A[i])

         return sum

思路：

一句话：某个Position能放多少水，取决于左右两边最小的有这个Position的位置高。

可以想象一下物理环境，一个位置要能存住水，就得保证这个Position处于一个低洼的位置。怎么才能满足低洼位置的条件呢？左右两边都得有比这个position高的元素。如何才能保证左右两边都有比这个position高的元素存在呢？只要左右两边的最大值中较小的一个比这个Position大就可以了。

巴特西

leetcode 【 Trapping Rain Water 】python 实现

最新文章

热门文章