第一篇 LeetCode(42)接雨水

LeetCode(42)接雨水

力扣官网

题目描述：给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

基本思路：

1. 基础解题思路：看到这道题时，应该要能够想到要遍历数组，关键是要如何遍历

遍历方法通常情况下有：单指针（从左往右或者从右往左或者二者结合），双指针（一个从左往右遍历，一个从右往左遍历），’二者结合‘的意思区别于双指针，’二者结合‘意思是一道题目里有一次遍历是从起点遍历到终点，还有一次遍历是从终点遍历到起点

2. 那要如何统计雨水量呢？不难想到是要边遍历边统计，且是要用一个数字去减当前遍历到的柱子高度，为什么？总雨水量是柱子间能够承接的雨水量的累加和。判断柱子间能够接多少水，注意我这里用到的词是柱子间，间！！所以遍历到第i个柱子的高度（height）时，我们要用一个数字去减遍历到的第i个柱子的高度height[i]。
3. 如何去确定这个数字是什么，是个难点！

题解:

方法一：动态规划

有没有一点思路了？用到了一个我们刚刚说的哪个遍历方法？没错，用到的是单指针,且是二者结合的方式，至于为什么，下面会说，先保留。

1. 第一次遍历：从左往右，每次遍历到一个值时，要做的是收集遍历到当前节点时遍历过程中的最大值，即官方给的代码中的leftMax[i] = Math.max(leftMax[i - 1], height[i]);

2. 第二次遍历：从右往左，每次遍历到一个值时，要做的是收集遍历到当前节点时遍历过程中的最大值，即官方给的代码中的rightMax[i] = Math.max(rightMax[i + 1], height[i]);

3. 还有一次遍历，结合刚刚收集到的leftMax数组，rightMax数组，以及height数组，遍历次数是height数组的长度，每遍历到一个i，要做的是统计雨水量了，对ans进行累加了！如何累加？每遍历到一个i，都会有一个height[i],一个leftMax[i],以及一个rightMax[i],通过刚刚第一点的分析，相信已经了解到了leftMax数组的第i个元素的含义，含义是什么，是从左往右遍历height数组时，从起点到第i个元素的height数组中的最大值。rightMax数组同理。

4. 判断柱子间能够接多少水，用的是leftMax[i]与rightMax[i]中的最小值去剪掉height[i],要理解用的这个数字是leftMax[i]与rightMax[i]中的最小值。如何理解，一个很好的方法就是实践！结合上面的图解+height数组，相信你能够理解了吧。因为是承接的水量是由两个柱子中最小的那根柱子来决定的（木桶效应）。

5. 为什么叫动态规划,leftMax[i] = Math.max(leftMax[i - 1], height[i]);rightMax[i] = Math.max(rightMax[i + 1], height[i]);发现什么规律没有，,leftMax[i]与rightMax[i]值的确定都跟leftMax[i - 1]跟(rightMax[i + 1]有关系，所以简单理解，就是第i个值的确定与第i-1个值有关系，即为动态规划，当然，动态规划不是这个定义，我概括的比较粗糙。

   

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

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

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

作者：力扣官方题解

方法二：单调栈

1. 该方法同样是使用单指针的方法，但是只用了一次遍历，从左往右遍历height数组。
2. 那么如何处理每一次遍历到的height[i]呢？入栈。入栈的数据是height数组的下标（0，1，2，3....），且并不是一开始就入栈，是要先处理一些情况，期间肯定包括怎么得到柱子间的雨水量。设计一种模式，只要栈不为空且遍历到的元素height[i]比栈顶元素大（’只要‘ 所以采用while循环），我们就删掉栈顶元素，这样子在每次遍历height数组前，栈都满足栈顶元素比上一个进栈的元素小（height[i]比栈顶元素小，不删栈顶元素，仅仅把height[i]放入栈中）。那么在遍历到height[i]比栈顶元素大时，此时就满足了两边（栈顶的上一个元素+遍历到的元素）高，中间（栈顶）低的情况了，用两边中最小的数字减掉中间（栈顶）数字，就可以得到currHeight了，再使用i - left - 1得到curWidth。二者相乘即可得到一个大的区间内雨水的承接量，注意，得到总雨水承接两要用累加。注意，这个过程要使用while操作。原因是只要满足两边高，中间低的情况，我们都要收集这个区间内的雨水承接量。while循环结束后，把下标放进栈中。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

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

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

作者：力扣官方题解

方法三：双指针

1. 该方法用到的是双指针。
2. 左指针遍历到height数组的每一个元素，更新遍历到的元素中的最大值leftMax。右指针遍历到height数组的每一个元素，更新遍历到的元素中的最大值rightMax。
3. 两种情况，如果左指针遍历到的元素比右指针遍历到的元素小height[left] < height[right]，那么就要用leftMax - height[left]得到两根柱子间的雨水承接量，同时左指针右移。这里要说明的是，为什么被减数是leftMax，因为在height[left] < height[right]情况下，肯定也满足了leftMax<rightMax，前面两种方法里，都涉及到了’两边高，中间低，用两边最小的数字减去中间的数字‘，这里同理。不一样的地方在于这里的两边不是中间柱子的左右两根柱子。建议用具体的height数组自己操演一遍，加深理解。
4. 右指针同理。

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}

作者：力扣官方题解

以上，是参考力扣官方解析，与自己的见解，如有错误，欢迎指正。

题外话：我觉得理解代码最好的方式是：自己举个例子，结合代码操演一遍，两遍，三遍........学习路上，希望你能发现java的魅力，并爱上java。