面试题 17.21. 直方图的水量

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 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

Python 解答：
1.两边收缩,最后一个测试用例超时

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        i = 1
        j = 0
        k = len(height)-1
        while j < k:
            while j < len(height) and height[j] < i:
                j += 1
            while k >= 0 and height[k] < i:
                k -= 1
            for m in range(j, k+1):
                if height[m] < i:
                    res += 1
            i += 1
        return res

2.双指针

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        i, j = 0, len(height)-1
        leftmax, rightmax = 0, 0
        res = 0
        while i < j:
            if height[i] > leftmax:
                leftmax = height[i]
            if height[j] > rightmax:
                rightmax = height[j]
            if leftmax < rightmax:
                res += leftmax - height[i]
                i += 1
            else:
                res += rightmax - height[j]
                j -= 1

        return res