[leetcode]Trapping Rain Water @ Python

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

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)。

代码:


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

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

时间: 06-12

[leetcode]Trapping Rain Water @ Python的相关文章

[LeetCode] [Trapping Rain Water 2012-03-10]

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 a

LeetCode: Trapping Rain Water [041]

[题目] 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

LeetCode: Trapping Rain Water 解题报告

https://oj.leetcode.com/problems/trapping-rain-water/ Trapping Rain WaterGiven 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,

[LeetCode] Trapping Rain Water II 收集雨水之二

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining. Note: Both m and n are less than 110. The height of each unit cell is greater th

LeetCode——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. The above elevation map is represented by a

Leetcode: Trapping Rain Water II

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining. Note: Both m and n are less than 110. The height of each unit cell is greater th

[LeetCode] Trapping Rain Water

Note: The following idea is in fact from the last answer in this link, which leads to a clean code. I just reorganize it and add some explanations. I hope it is Ok. The following are four solutions in C/C++/Java/Python respectively. The basic idea is

[LeetCode] 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. The above elevation map is represented by a

leetcode Trapping Rain Water pthon

class Solution(object): def trap(self,nums): leftmosthigh = [0 for i in range(len(nums))] leftmax=0 for i in range(len(nums)): if nums[i] > leftmax: leftmax=nums[i] leftmosthigh[i] = leftmax print leftmosthigh sums=0 rightmax=0 for i in reversed(rang