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
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.
Solution:
class Solution: # @param A, a list of integers # @return an integer def trap(self, A): max = 0 maxIndex = 0 for i in range(0,len(A)): if A[i] > max: max = A[i] maxIndex = i previousMax = 0 count = 0 for i in range(0, maxIndex): if A[i] > previousMax: previousMax = A[i] count += previousMax - A[i] previousMax = 0 for i in range(len(A)-1, maxIndex, -1): if A[i] > previousMax: previousMax = A[i] count += previousMax - A[i] return count
No comments :
Post a Comment