class Solution:
    def trap(self, height: List[int]) -> int:
        Sum = sum(height) # 得到柱子的体积
        size = len(height) 
        left, right = 0, size - 1 # 双指针初始化
        volume, high = 0, 1 # 总体积和高度初始化
        while (left <= right):
            while (left <= right and height[left] < high): 
                left += 1 
            while (left <= right and height[right] < high):
                right -= 1
            volume += right - left + 1 # 每一层的容量都加起来
            high += 1 # 高度加一
        return volume - Sum # 总体积减去柱子体积，即雨水总量

数组 困难 双指针法妙啊！

我想到了按层计算水量，但是时间复杂度O(n),无法通过最后一个测试

https://leetcode-cn.com/problems/volume-of-histogram-lcci/

👇O(n)的屑代码

class Solution:
    def trap(self, height: List[int]) -> int:
        d = dict()
        ans = 0
        for i,n in enumerate(height):
            for j in range(1,n+1):
                if j in d:
                    ans += (i - d[j][-1] - 1)
                    d[j].append(i)
                else:
                    d[j] = [i]
        return ans