Advertisement
lichenran1234

trap rain water

Apr 11th, 2021
234
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.85 KB | None | 0 0
  1. class Solution(object):
  2.     def trap(self, height):
  3.         """
  4.        :type height: List[int]
  5.        :rtype: int
  6.        """
  7.         if height is None or not height:
  8.             return 0
  9.        
  10.         left = 0
  11.         right = len(height) - 1
  12.        
  13.         cur_max_left = 0
  14.         cur_max_right = 0
  15.        
  16.         result = 0
  17.        
  18.         while right >= left:
  19.             if height[left] <= height[right]:
  20.                 if height[left] > cur_max_left:
  21.                     cur_max_left = height[left]
  22.                 result += max(cur_max_left - height[left], 0)
  23.                 left += 1
  24.             else:
  25.                 if height[right] > cur_max_right:
  26.                     cur_max_right = height[right]
  27.                 result += max(cur_max_right - height[right], 0)
  28.                 right -= 1
  29.        
  30.         return result
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement