LeetCode刷题笔记：字节跳动-数组和排序(10)-接雨水

10.接雨水

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

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

本题起初设置了两个指针，两个指针间隔2个单位。右侧指针先向右遍历，如果右侧指针的下一个位置比当前位置高度更高，则右侧指针向右移动。当右侧指针的下一个位置没有当前位置高时，计算两个指针高度的差值乘以宽度，然后减去中间高度的总和。不过该代码超出时间限制，代码如下：

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l,r=0,2
        res = 0
        le = len(height)
        while l=height[l]:
                l+=1
                r+=1
                continue
            if height[r]>=height[l]:
                tmp = (r-l-1)*height[l]-sum(height[l+1:r])
                if tmp>0:
                    res +=tmp
                l,r = r,r+2
            else:
                lef = height[l+1:]
                mx = max(lef)
                if mx>=height[l]:
                    r+=1
                    continue
                else:
                    lef = lef[::-1]
                    idx = lef.index(mx)
                    r = le-idx-1
                    tmp = (r-l-1)*height[r]-sum(height[l+1:r])
                    res+=tmp
                    l = r
                    r +=2
        return res

换一种思路对该题进行解答。首先雨水存储的条件是左右两边都高于中间，也就是形成一个凹槽，那么就是要找凹槽的左边界和右边界。我们可以找寻最高的那个柱子作为一个边界，然后设置左右指针，分别指向开头和结尾。由于已经有一个最高的柱子作为边界，所以只要另一个边界大于中间柱子的高度值，即可形成凹槽。这时可以将左指针向右移动，直到遇到最高的那个柱子为止，设置左侧边界最高值为0.如果当前柱子高度大于左侧边界最高值，则更新左侧边界最高值，如果小于左侧边界最高值，则当前凹槽的储水量就是左侧边界最高值减去当前柱子的高度。为什么是左侧边界最高值减去当前柱子的高度？因为咱们一开始找寻的是整体中最高的柱子，所以剩下的柱子都比它矮，因此凹槽的边界高度就由左侧边界最高值确定。然后将右指针向左移动，具体操作与左指针相同。该代码通过所有测试用例，代码如下：

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if height==[]:
            return 0
        idx = height.index(max(height))
        l,r = 0,len(height)-1
        lh,rh = 0,0
        res =0
        while lidx:
            rh=max(rh,height[r])
            res += rh-height[r]
            r-=1
        return res