Description: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Link: 42. Trapping Rain Water

Examples:

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

思路: 遍历每个位置可储存的雨水，比如[4, 2, 8], 在位置 i = 1, height[i] = 2上, 位置i左边的最高处max_left[i]，右边的最高处max_right[i]，位置i的储存雨水量=min(max_left[i], max_right[i]) - height[i]. 所以我们就用两个数组记录每个位置i的左右边最高处的高度，然后遍历叠加。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height: return 0
        n = len(height)
        max_left = [0]*n
        max_right = [0]*n
        for i, h in enumerate(height):
            max_left[i] = max(max_left[i-1], height[i])
        max_right[-1] = height[-1]
        i = n - 2
        while i >= 0:
            max_right[i] = max(max_right[i+1], height[i])
            i -= 1
        res = 0
        for i, h in enumerate(height):
            res += max(0, (min(max_left[i], max_right[i]) - h))
        return res       

日期: 2021-04-24 前天和昨天都没有做题，最近学习的热情越来越....马上要deadline了，procrastination