Question: http://oj.leetcode.com/problems/trapping-rain-water/
Question Name: Trapping Rain Water
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | class Solution: # @param A, a list of integers # @return an integer def trap(self, A): water = 0 # The total number of water # The the first decreasing point begin = 0 while begin < len(A) - 1 and A[begin] <= A[begin + 1]: begin += 1 # The array A is always non-decreasing. No where to store water if begin >= len(A) - 1: return 0 stack = [(begin, A[begin])] for wall in enumerate(A[begin+1:], begin+1): # Does not make additional space to store water. AND does not # change the landscape if wall[1] == stack[-1][1]: continue # Does not make additional space to store water. BUT does # change the landscape elif wall[1] < stack[-1][1]: stack.append(wall) # Add some additional space to store water. # We need to adjust the landscape. For example, the previous # landscape is:# , with a new #. Firstly, we will fill the gap # ## # # ## # # ### # # like # # to # # to #++# and finally compress to # # ## # ##+# ##+# # # ## # ##+# ##+# # # #### #### #### # else: adjustIndex = -1 while len(stack) > 1 and wall[1] > stack[-1][1]: preWall = stack.pop() # Fill with water water += (min(wall[1], stack[-1][1]) - preWall[1]) * (wall[0]-preWall[0]) # Compress the walls with the same height adjustIndex = preWall[0] # Left guard wall is abandoned, because we have a new one if len(stack) == 1 and stack[-1][1] <= wall[1]: stack.pop() stack.append((adjustIndex, wall[1])) return water |