题目: 接雨水

来自智得网
跳转至： 导航、​ 搜索

分析

穷举法

每根柱子可以接到多少雨水和三个值有关，

当前柱子的高度 height[i]，当前柱子左侧柱子中最高柱子的高度 leftHeight，当前柱子右侧柱子中最高柱子的高度 rightHeight。

当前柱子两侧的最高值中的较低值 lower 构成了柱子的贮水高度，如果该较低值高于当前柱子的高度，该柱子可以贮水的值是 lower - height[i] , 否则贮水量为0。

穷举法可以遍历所有的柱子，计算每根柱子的贮水量，将这些贮水量相加就可以得出下雨之后这些柱子一共可以接的雨水量。

穷举法遍历了所有的柱子，该遍历的时间复杂度是O（n）。

计算每根柱子贮水量的时候计算左右两侧最高值也需要遍历所有的柱子，所以该过程的时间复杂度也是O（n）。

内外两层循环总的时间复杂度是O（n2）。

动态规划

穷举法每计算一次当前柱子的贮水量，需要计算当前柱子左侧以及右侧柱子的最高值。

但如果当前柱子的左侧那一根柱子的左侧最高值已经有计算结果的情况下，只需要比较该左侧最高值和左侧那一根柱子的高度，其中的最高值就是当前柱子左侧的最高值。

所以该问题是一个最优子结构问题，可以使用动态规划进行求解。

动态规划一般分为确定变量，确定状态转移方程，确定边界条件等三个步骤：

该问题中的变量就是当前位置 i ，我们需要求解当前位置左侧的最高值（leftHighest[i]）以及当前位置右侧的最高值（rightHighest[i]）。

如果已经求得 leftHighest[i-1] 的值，leftHighest[i] 的值是leftHighest[i-1]和 height[i-1] 中的较高值，同理 rightHighest[i] 的值是 rightHighest[i+1] 和 height[i-1]中的最高值。

该问题的边界条件是leftHighest[0]以及rightHighest[height.length-1]都等于0。

综上所述，该问题的状态转移方程是：

双指针

动态规划存储了两个数组，分别是左侧最高值的数组，右侧最高值的数组，但是实际上计算过程中值需要最近的左侧最高值以及右侧最高值，所以使用双指针可以对动态规范的空间复杂度进行进一步优化。

双指针分别指向柱子头尾两端。

比较两个指针指向的柱子的高度，其中一个柱子较低，另一个柱子较高。

需要将较低柱子的指针向中间移动

题解

穷举法

public class Solution {
    public int solute(int[] height) {
        int sum = 0;
        // 两侧的柱子无法贮水。下标从 1 到 length - 2进行循环。
        for (int i = 1; i < height.length - 1; i++) {
            int leftHighest = 0;
            // 遍历左侧最高值
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] > leftHighest) {
                    leftHighest = height[j];
                }
            }
            int rightHighest = 0;
            // 遍历右侧最高值
            for (int j = i + 1; j < height.length; j++) {
                if (height[j] > rightHighest) {
                    rightHighest = height[j];
                }
            }
            int lower = Math.min(leftHighest, rightHighest);
            // 两侧最高值中较低的柱子也比当前柱子高的时候，柱子才可以贮水
            if (lower > height[i]) {
                sum = sum + (lower - height[i]);
            }
        }
        return sum;
    }
}

动态规划

public class Solution {
    public static int solute(int[] height) {
        int sum = 0;
        int[] leftHighest = new int[height.length];
        int[] rightHighest = new int[height.length];

        for (int i = 1; i < height.length - 1; i++) {
            leftHighest[i] = Math.max(leftHighest[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            rightHighest[i] = Math.max(rightHighest[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(leftHighest[i], rightHighest[i]);
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
        
    }
}

双指针

public class Solution {
    public static int solute(int[] height) {
        int sum = 0;
        int leftHighest = 0;
        int rightHighest = 0;
        
        // 左右指针
        int left = 1;
        int right = height.length - 2;
        for (int i = 1; i < height.length - 1; i++) {
            if (height[left - 1] < height[right + 1]) {
                leftHighest = Math.max(leftHighest, height[left - 1]);
                int min = leftHighest;
                if (min > height[left]) {
                    sum = sum + (min - height[left]);
                }
                left++;
            } else {
                rightHighest = Math.max(rightHighest, height[right + 1]);
                int min = rightHighest;
                if (min > height[right]) {
                    sum = sum + (min - height[right]);
                }
                right--;
            }
        }
        return sum;
    }
}
取自“https://www.aigetting.com/index.php?title=题目:接雨水&oldid=2061”