[数据结构与算法]力扣42题：接雨水

给定?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 个单位的雨水（蓝色部分表示雨水）。?
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答：

方法一：暴力解

package lc.lc42;


public class FirstSolution {

    // 暴力解法
    public int trap(int[] height) {
        if (height == null) {
            return -1;
        }
        // 找到第一个下降的地方 且 大于 preDownPos所在位置height的地方
        int res = 0;
        int preDownPos = -1;
        boolean beginComputeFlag = false;
        for (int i = 1; i < height.length; i++) {
            if (!beginComputeFlag) {
                if (height[i] < height[i - 1]) {
                    preDownPos = i - 1;
                    beginComputeFlag = true;
                }
            } else {
                // 找上升最高点
                int maxHeightThanPre = -1;
                for (int j = i; j < height.length; j++) {
                    if (height[j] >= height[preDownPos]) {
                        maxHeightThanPre = j;
                        break;
                    }
                }
                if (maxHeightThanPre != -1) {
                    for (int j = maxHeightThanPre + 1; j < height.length; j++) {
                        if (height[j] >= height[maxHeightThanPre]) {
                            maxHeightThanPre = j;
                        } else {
                            break;
                        }
                    }
                }
                if (maxHeightThanPre != -1) {
                    for (int j = preDownPos + 1; j < maxHeightThanPre; j++) {
                        if (height[preDownPos] - height[j] > 0) {
                            res += height[preDownPos] - height[j];
                        }
                    }
                    beginComputeFlag = false;
                    i = maxHeightThanPre;
                } else {
                    if (height[i] > height[i - 1] && i == height.length - 1 ||
                            height[i] > height[i - 1] && height[i] >= height[i + 1]) {
                        int firstBigHeightPos = i;
                        for (int j = i + 1; j < height.length; j++) {
                            if (height[j] >= height[firstBigHeightPos]) {
                                firstBigHeightPos = j;
                            }
                        }
                        // 计算一下雨水量
                        int computeBaseHeight = Math.min(height[preDownPos], height[firstBigHeightPos]);
                        for (int j = preDownPos + 1; j < firstBigHeightPos; j++) {
                            if (computeBaseHeight - height[j] > 0) {
                                res += computeBaseHeight - height[j];
                            }
                        }
                        // 重置beginComputeFlag
                        beginComputeFlag = false;
                        i = firstBigHeightPos;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        FirstSolution firstSolution = new FirstSolution();
        int[] height = {7, 7, 0, 4, 0, 6, 8, 5, 1, 6, 0, 4, 7, 0, 0, 1};
        System.out.println(firstSolution.trap(height));
    }
}

方法二：动态规划

package lc.lc42;


public class SecondSolution {
    // 动态规划
    public int trap(int[] height) {
        if (height == null) {
            return -1;
        }
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        int maxVal = Integer.MIN_VALUE;
        for (int i = 0; i < height.length; i++) {
            if (height[i] > maxVal) {
                maxVal = height[i];
            }
            leftMax[i] = maxVal;
        }
        maxVal = Integer.MIN_VALUE;
        for (int i = height.length - 1; i >= 0; i--) {
            if (height[i] > maxVal) {
                maxVal = height[i];
            }
            rightMax[i] = maxVal;
        }
        int res = 0;
        for (int i = 1; i < height.length - 1; i++) {
            int tempVal = Math.min(leftMax[i], rightMax[i]);
            res += Math.max(tempVal - height[i], 0);
        }
        return res;
    }

    public static void main(String[] args) {
        SecondSolution solution = new SecondSolution();
        int[] test = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(solution.trap(test));
    }
}

这里的动态规划挺巧妙的，用了两个数组来统计，我刚开始在想如何用动态规划来做的时候，想的是用一个二维数组，但是这样的话不就又是很高的时间复杂度了吗，其实可以把问题拆解一下，用两个数组来做这一题应该是很灵活的方法。