暴力解法

确定每个列所能装载的水容量，累加即可得到结果。
每个列所能装载的水容量步骤如下：

1. 获得左边最高的高度 maxLeft。
2. 获得右边最高的高度 maxRight。
3. 得到最小值 minH = Math.max(maxLeft, maxRight);
4. 当前柱子所能承载的水容量 = minH - 柱子高度

注意，最左和最右柱子是不会装载水，所以在遍历时剔除。

public int trap(int[] height) {
    // 解法一：暴力解
    int res = 0;
    // 注意，最左和最右是不会盛水的
    for (int i = 1; i < height.length-1; i++) {
        // 找左边最高的位置
        int maxLeft = 0;
        for (int j = i-1; j >= 0; j--) {
            maxLeft = Math.max(maxLeft, height[j]);
        }
        // 找右边最高的位置
        int maxRight = 0;
        for (int j = i + 1; j < height.length; j++) {
            maxRight = Math.max(maxRight, height[j]);
        }
        int minHeight = Math.min(maxLeft, maxRight);
        if (minHeight > height[i]) {
            res += (minHeight - height[i]);
        }
    }
    return res;
}

动态规划

暴力解法中我们每次都需要向左、向右找出柱子最高的高度，我们不妨使用一个数组将柱子 i 左边最高高度和右边最高高度存起来，递推式如下：

int[] maxLeft = new int[length];
int[] maxRight = new int[length];
maxLeft = Math.max(maxLeft[i-1], height[i-1]);
maxRight = Math.max(maxRight[i+1], height[i+1]);

双指针

动态规划中，我们常常可以对空间复杂度进一步优化。
双指针法真的妙，那么如何理解双指针法呢？听我来给你捋一捋。（捋的过程和原解中的C++在细节方面的处理是有出入的）
我们先明确几个变量的意思：
leftmax：左边的最大值，它是从左往右遍历找到的 rightmax：右边的最大值，它是从右往左遍历找到的 left：从左往右处理的当前下标 right：从右往左处理的当前下标
定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。
定理二：当我们从左往右处理到left下标时，左边的最大值leftmax对它而言是可信的，但rightmax对它而言是不可信的。（见下图，由于中间状况未知，对于left下标而言，rightmax未必就是它右边最大的值）
定理三：当我们从右往左处理到right下标时，右边的最大值rightmax对它而言是可信的，但leftmax对它而言是不可信的。
rightmax leftmax | | | |_ ?????????????????????? | | | || | | left right
对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，这时候，如果left_max<right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。 所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。

class Solution:
    def trap(self, height: List[int]) -> int:
        left=0
        right=len(height)-1
        left_max=right_max=0
        ans=0
        while left<=right:
            if left_max<right_max:
                ans+=max(0,left_max-height[left])
                left_max=max(left_max,height[left])
                left+=1
            else:
                ans+=max(0,right_max-height[right])
                right_max=max(right_max,height[right])
                right-=1
        return ans

单调递减栈

// 单调递减栈
public int trap(int[] height) {
    int res = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[stack.peekLast()] < height[i]) {
            // 右柱子大小栈顶元素，可计算栈顶元素对应的部分雨水容量
            int popIndex = stack.pollLast();
            if (stack.isEmpty()) break; // 栈为空，说明已经计算完成
            int width = i - stack.peekLast() - 1;
            int h = Math.min(height[stack.peekLast()], height[i]);
            res += width * (h - height[popIndex]);
        }
        stack.addLast(i);
    }
    return res;
}