题解一：

        按列求：分别考虑每一列的雨水高度，某列的雨水高度只与其左侧最高墙和右侧最高墙有关，一种情况是该列比左右侧的墙都低，则根据木桶效应该列雨水高度为min(左侧墙高，右侧墙高)-列高，而其余情况该列均无法接住雨水。找左右侧最高墙时可以用动态规划进行优化，对于第n列，左侧最高墙为max(第n-1列的左侧最高墙，第n-1列高度)，右侧最高墙为max(第n+1列的右侧最高墙，第n+1列高度)，最后将每列的雨水高度相加即可。

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int water = 0;
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = 0;
        right[len - 1] = 0;


        for (int i = 1; i < len; i++) {
            left[i] = Math.max(left[i - 1], height[i - 1]);
        }
        for (int i = len - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i + 1]);
        }

        for (int i = 1; i < len - 1; i++) {
            if (height[i] < left[i] && height[i] < right[i]) water += Math.min(left[i], right[i]) - height[i];
        }

        return water;
    }
}

题解二：

        单调栈：由于只有凹型结构可以接住雨水，因此我们可以找出高度图中的所有凹型结构，计算接住雨水的量总和。我们利用单调栈来求解，要满足凹型结构则需要至少三根柱子，并且高度呈先递减后递增的趋势。遍历数组依次入栈，如果是递减结构则继续入栈，如果出现递增，则判断是否满足凹型结构（栈中至少有两个元素），如果不满足则说明只能形成两根递增结构的柱子，此时将左柱子出栈，如果满足则根据水桶效应计算三个柱子能接住的雨水量，并将中部柱子出栈。以下是官方给出的动画演示（来源. - 力扣（LeetCode））

import java.util.Stack;

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        Stack<Integer> stack = new Stack<>();
        int water = 0;
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int temp = stack.pop();
                if (stack.isEmpty()) break;
                else {
                    int left = stack.peek();
                    water += (i - left - 1) * (Math.min(height[i], height[left]) - height[temp]);
                }
            }
            stack.push(i);
        }
        return water;
    }
}