LeetCode刷题【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

提示：

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

刷动态规划重新做到这一题，之前写的是基于单调队列的，可以看下之前的文章，LeetCode刷题【42】接雨水

重新审视下这题，某个位置能存储的最大雨量依赖于他的左侧的最大值和他右侧的最大值这两个值中的较小的一个值。那么怎么取到左侧的最大值和右侧的最大值呢？

• 从左往右依次比较保存最大值就是某个位置的左侧的最大值
• 从右往左依次比较保存最大值就是某个位置右侧的最大值

在这样的情况下，我们建立一个二维数组，dp[i][2]，其中dp[i][0]表示该位置左侧的最大值，dp[i][1]表示该位置右侧的最大值。这样对应的i位置能存储的最大水量就是

min(dp[i][0],dp[i][1])-height[i]

转移方程已经确定的情况下那么代码也就非常容易写出来了

class Solution {
    public int trap(int[] height) {
        int count = 0;
        int[][] dp = new int[height.length][2];
        int idxLeft = 0;
        int idxRight = height.length - 1;

        dp[idxLeft][0] = height[idxLeft];
        dp[idxRight][1] = height[idxRight];
        idxLeft++;
        idxRight--;
        for (; idxLeft < height.length; idxLeft++) {
            dp[idxLeft][0] = Math.max(dp[idxLeft-1][0],height[idxLeft]);
            dp[idxRight][1] = Math.max(dp[idxRight+1][1],height[idxRight]);
            if (idxLeft>=idxRight){
                count += Math.min(dp[idxLeft][0],dp[idxLeft][1]) - height[idxLeft];
                count += Math.min(dp[idxRight][0],dp[idxRight][1]) - height[idxRight];
            }
            idxRight--;
        }
        if (height.length%2==1){
            int mid = height.length >> 1;
            count -= Math.min(dp[mid][0],dp[mid][1]) - height[mid];
        }
        return count;
    }
}

这段代码，在一次遍历的过程中同时更新左侧的最大值和右侧的最大值，当两侧往中间靠拢的时候，如果在中间相遇了，那么就可以开始统计了。

后面有一段如果height数组长度为基数，中间值会重复计算一遍所以需要减去