题目描述

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

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

题目分析

动态规划

每个位置 i 能接到多少雨水，取决于它左边的最高点和右边的最高点，取相对较低的那个，假设为 h。h > height[i] 时，能接到水量为 h – height[i].
使用数组维护所有左区间的最高点和右区间的最高点，就可以进一步计算每个位置能接到的水量，累加在一起即可。
时间复杂度 O(n)，空间复杂度 O(n)

双指针（推荐）

和前面思想一致，只是把从左到右按顺序枚举，变成从两端向内枚举最高点较小的那个。
使用双指针 l, r 从两端维护 [0, l] 的最大值 maxL 和 [r, n-1] 的最大值 maxR.
任一时刻，对于 maxL 和 maxR 中较小的值所在的格子，最大水位已经确定，即 min(maxL, maxR)，计算后将被计算的指针位置向内移动一位即可
时间复杂度 O(n)，空间复杂度 O(1)

单调栈

单调栈，栈内存储数组下标。
从左向右枚举数组，高度小于等于栈顶时入栈。枚举高度大于栈顶时，说明当前位置是右边界，栈顶是相对底部，此时将栈顶出栈，新的栈顶为左边界。
不断循环直到所有小于当前值的都出栈，此时新的栈顶仍然是左边界，因此再计算一次容量但无需出栈。最后把当前位置入栈，继续枚举下一个位置。
每次只填满当前能看到的横向接水区域，纵向如果还存在空间，会在后面的计算中补充上。
时间复杂度 O(n)，空间复杂度 O(n)

Java

public int trap1(int[] height) {
    int sum = 0;
    int size = height.length;
    int[] leftHeight = new int[size];
    leftHeight[0] = height[0];
    for (int i = 1; i < size; i++) {
        leftHeight[i] = Math.max(leftHeight[i - 1], height[i]);
    }

    int[] rightHeight = new int[size];
    rightHeight[size - 1] = height[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        rightHeight[i] = Math.max(rightHeight[i + 1], height[i]);
    }

    for (int i = 0; i < size; i++) {
        int h = Math.min(leftHeight[i], rightHeight[i]);
        if (h > height[i]) {
            sum += h - height[i];
        }
    }
    return sum;
}

public int trap2(int[] height) {
    int sum = 0;
    int size = height.length;
    int l = 0, r = size - 1;
    int maxL = 0, maxR = 0;
    while (l <= r) {
        maxL = Math.max(height[l], maxL);
        maxR = Math.max(height[r], maxR);
        if (maxL <= maxR) {
            sum += maxL - height[l];
            l++;
        } else {
            sum += maxR - height[r];
            r--;
        }
    }
    return sum;
}

public int trap3(int[] height) {
    int sum = 0;
    Deque<Integer> stack = new LinkedList<>();
    stack.push(0);
    for (int i = 1; i < height.length; i++) {
        int curH = height[i];
        while (!stack.isEmpty()) {
            int top = stack.peek();
            if (curH > height[top]) {
                int r = i;
                int bottom = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int l = stack.peek();
                int h = Math.min(height[l], height[r]) - height[bottom];
                int w = r - l - 1;
                sum += h * w;
            } else {
                break;
            }
        }
        stack.push(i);
    }

    return sum;
}

Kotlin

fun trap(height: IntArray): Int {
    var ans = 0
    var l = 0
    var r = height.size - 1
    var maxL = 0
    var maxR = 0

    while (l <= r) {
        maxL = maxL.coerceAtLeast(height[l])
        maxR = maxR.coerceAtLeast(height[r])
        if (maxL <= maxR) {
            ans += maxL - height[l]
            l++
        } else {
            ans += maxR - height[r]
            r--
        }
    }
    return ans
}