LeetCode-42-接雨水

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

image.png
image.png

解题思路：

1. 暴力求解，遍历height数组，当遍历到i时，从点分别向两边遍历求左边最大值left_max和右边最大值right_max，接多少雨水由两边最大值的最小值决定，即min(left_max, right_max)，然后减去height[i]的值即可，就是该点i可接雨水数；
2. 双指针法：略。

class Solution: 
    def trap(self, height: List[int]) -> int:
        # n = len(height)
        # y = 0
        # for i in range(1, n-1):
        #     x = min(max(height[0:i]), max(height[i+1:n]))
        #     y += x-height[i] if x > height[i] else 0
        # return y
        n = len(height)
        left=0
        right=n-1
        l_max = 0
        r_max = 0
        res = 0
        while left<right:
            l_max = max(l_max, height[left])
            r_max = max(r_max, height[right])
            
            if l_max < r_max:
                res += l_max- height[left]
                left+=1
            else:
                res += r_max - height[right]
                right-=1
        return res