【leetcode刷题】T31-接雨水

【英文题目】（学习英语的同时，更能理解题意哟~）

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.

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.Thanks Marcosfor contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

【中文题目】

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

【思路】

需要找到图中所有“凹”的地方，不断找最大值和次大值，求得中间“凹”的面积。

有一个很妙的方法：给定两个指针l和r，分别指向第0个元素和最后1个元素，同时给定两个变量leftmax和rightmax，存储0-l区间最大值和r-末尾区间最大值。当height[l] < height[r]时，由于height[l]同时小于leftmax（leftmax的下标小于等于l），相当于l处于“凹”处，可以计算接水的面积，l自增1；同理，height[l] >= height[r]时，由于height[r] <= rightmax，可累加接水面积，r自减1。重复以上步骤，直到l > r。

【代码】

python版本

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if len(height) < :
            return 
        l, r = , len(height) - 
        leftmax, rightmax = height[l], height[r]
        res = 
        while l <= r:
            if height[l] < height[r]:
                leftmax = max(leftmax, height[l])
                # height[l] <= leftmax && height[l] < height[r]
                res += (leftmax - height[l])
                l += 
            else:
                rightmax = max(rightmax, height[r])
                # height[r] <= righttmax && height[r] <= height[l]
                res += (rightmax - height[r])
                r -= 
        return res