首页 > 移动平台 > 详细

[leetcode]Trapping Rain Water @ Python

时间:2014-06-12 23:34:44      阅读:534      评论:0      收藏:0      [点我收藏+]

标签:class   代码   java   style   int   src   

原题地址:https://oj.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.

bubuko.com,布布扣

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!

解题思路:模拟法。开辟一个数组leftmosthigh,leftmosthigh[i]为A[i]之前的最高的bar值,然后从后面开始遍历,用rightmax来记录从后向前遍历遇到的最大bar值,那么min(leftmosthigh[i], rightmax)-A[i]就是在第i个bar可以储存的水量。例如当i=9时,此时leftmosthigh[9]=3,而rightmax=2,则储水量为2-1=1,依次类推即可。这种方法还是很巧妙的。时间复杂度为O(N)。

代码:

bubuko.com,布布扣
class Solution:
    # @param A, a list of integers
    # @return an integer
    def trap(self, A):
        leftmosthigh = [0 for i in range(len(A))]
        leftmax = 0
        for i in range(len(A)):
            if A[i] > leftmax: leftmax = A[i]
            leftmosthigh[i] = leftmax
        sum = 0
        rightmax = 0
        for i in reversed(range(len(A))):
            if A[i] > rightmax: rightmax = A[i]
            if min(rightmax, leftmosthigh[i]) > A[i]:
                sum += min(rightmax, leftmosthigh[i]) - A[i]
        return sum
bubuko.com,布布扣

 

[leetcode]Trapping Rain Water @ Python,布布扣,bubuko.com

[leetcode]Trapping Rain Water @ Python

标签:class   代码   java   style   int   src   

原文:http://www.cnblogs.com/zuoyuan/p/3781453.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号