LeetCode：42. 接雨水（困难）

问题链接

42. 接雨水（困难）

问题描述

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

示例

解题思路

1.暴力解法：求每一列的雨水

遍历每一列（起始列和最后一列除外，因为不可能有雨水）：
往左右分别扩散，找到左、右边界的最高高度；
根据左、右最高高度以及当前柱形的高度，可以算出当前列存在的雨水。

2.动态规划

解1是一种暴力解法，但是找左右最高边界求每一列的思路是可以借鉴的；
解2是在这个思路的基础上，用动态规划来做优化：
A. 求最左边界：遍历数组，第i位的左最高边界就是max(第i-1位的左最高边界, 第i-1位的高度);
B. 求最右边界同理；
C. 再用一次遍历进行雨水求和。

3.单调栈

推荐阅读：【动画模拟】一下就能读懂（单调栈）
原理：当几个柱形形成了“U”型时，就计算一次面积
遍历数组，将数组中的数丢到单调递减栈里，当新进的数违反了单调性（新进的数大于栈顶元素），就计算一次面积：
A. 取出栈顶元素，作为矩形的下边界，记为low;
B. 继续查看栈顶元素：如果和原来的栈顶元素一样大，直接取出来；直到找到比原栈顶元素大的数，记为high;
C. 根据low、high以及遍历数组当前的位置，计算面积：(Math.min(height[i], height[high]) - height[low]) * (i - high - 1)。

4.基于解法1、解法2的思路，用双指针进行优化

这里不赘述，感觉看代码理解起来更快。。。

代码示例（JAVA）

1.暴力解法

class Solution {
    public int trap(int[] height) {
        int result = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int left = 0, right = 0;
            for (int j = i - 1; j >= 0; j--) {
                left = Math.max(left, height[j]);
            }
            for (int j = i + 1; j <= height.length - 1; j++) {
                right = Math.max(right, height[j]);
            }
            if (Math.min(left, right) > height[i]) {
                result += Math.min(left, right) - height[i];
            }
        }
        return result;
    }
}

时间复杂度：O(n²)
执行结果

2.动态规划

class Solution {
    public int trap(int[] height) {
        int[] left = new int[height.length];
        int[] right = new int[height.length];

        // 左边界
        for (int i = 0; i < height.length; i++) {
            left[i] = i == 0 ? 0 : Math.max(left[i - 1], height[i - 1]);
        }
        // 右边界
        for (int j = height.length - 1; j >= 0; j--) {
            right[j] = j == height.length - 1 ? 0 : Math.max(right[j + 1], height[j + 1]);
        }
        // 求和
        int result = 0;
        for (int i = 0; i < height.length; i++) {
            if (Math.min(left[i], right[i]) - height[i] > 0) {
                result += Math.min(left[i], right[i]) - height[i];
            }
        }

        return result;
    }
}

时间复杂度：O(n)
执行结果

image.png

3.单调递减栈

class Solution {
    public int trap(int[] height) {
        Deque<Integer> deque = new LinkedList<>();

        int result = 0;
        for (int i = 0; i < height.length; i++) {
            // 破坏单调递减，找雨水面积
            while (!deque.isEmpty() && height[deque.peekLast()] < height[i]) {
                int low = deque.pollLast();
                // 移除和low相同高度的，找到第一个比low高的位置
                while (!deque.isEmpty() && height[deque.peekLast()] == height[low]) {
                    deque.removeLast();
                }
                if (!deque.isEmpty()) {
                    int high = deque.peekLast();
                    // 计算面积
                    result += (Math.min(height[i], height[high]) - height[low]) * (i - high - 1);
                }
            }
            // 入栈
            deque.offerLast(i);
        }
        
        return result;
    }
}

时间复杂度：O(n)
执行结果

4.双指针

class Solution {
    public int trap(int[] height) {
        int maxLeft = 0, maxRight = 0;
        int left = 0, right = height.length - 1;

        int result = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] > maxLeft) {
                    maxLeft = height[left];
                } else {
                    result += maxLeft - height[left];
                }
                left++;
            } else {
                if (height[right] > maxRight) {
                    maxRight = height[right];
                } else {
                    result += maxRight - height[right];
                }
                right--;
            }
        }

        return result;
    }
}

时间复杂度：O(n)
执行结果