Fork me on GitHub

Trapping Rain Water

Posted on

Description

https://leetcode.com/problems/trapping-rain-water/description/

Solution

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
class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_left = [0 for i in range(len(height))] 
        maximun_left = - 1
        for index in range(0, len(height) - 1):
            if height[index] > maximun_left:
                maximun_left = height[index]
            max_left[index + 1] = maximun_left
        
        max_right = [0 for i in range(len(height))]
        maximun_right = -1
        for index in range(len(height) - 1, 0, -1):
            if height[index] > maximun_right:
                maximun_right = height[index]
            max_right[index - 1] = maximun_right
           
        ##Traverse all the index
        ret = 0
        for i in range(len(height)):
            bar = min(max_left[i], max_right[i])
            if bar > height[i]:
                ret += (bar - height[i])
                
        return ret