leetcode力扣经典问题——42.接雨水

42.接雨水

题目描述：

 1.按行计算

思路：求第 i 层的水，遍历每个位置，如果当前的高度小于 i ，并且两边有高度大于等于 i 的，说明这个地方一定有水，水就可以加 1。

总水量可以用sum变量统计，再用一个temp变量表示当前累积的水，

如果求高度为 i 的水，首先用一个变量 temp 保存当前累积的水，从左到右遍历墙的高度，遇到高度大于等于 i 的时候，开始更新 temp。更新原则是遇到高度小于 i 的就把 temp 加 1，遇到高度大于等于 i 的，就 sum += temp ，并且 temp 置零，然后继续循环。

逐个按行计算，先求第一行的水有多少个单位

 计算第1行的水，数组为height= [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ];

规则是当temp开始更新时，高度小于1，temp++；高度大于等于1，sum += temp，temp = 0；

初始设置temp = 0；sum = 0；

height[0] = 0 < 1 , 不更新;

height[1] = 1 >= 1 , 开始更新temp；

height[2] = 0 < 1 , temp ++ , temp = 1;

height[3] = 2 >= 1 , sum += temp = 1, temp = 0;

height[4] = 1 >= 1 , sum += temp =1, temp = 0;

height[5] = 0 < 1 , temp ++ , temp = 1;

height[6] = 1 >= 1 , sum += temp = 2 , temp = 0;

剩余height[7]到最后都大于等于1,sum += temp = 2,temp = 0;

结束第一轮循环时，sum = 2；

再求第二行的水

数组为height= [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ];

规则是当temp开始更新时，高度小于2，temp++；高度大于等于1，sum += temp，temp = 0；

此时sum=2，初始化temp=0；

height[0] 等于 0 < 2，不更新；

height[1] 等于 1 < 2，不更新；

height[2] 等于 0 < 2，不更新；

height[3] 等于 2 >= 2，开始更新temp；

height[4] 等于 1 < 2，tem ++ ，temp = 1；

height[5] 等于 0 < 2，temp ++ ，temp = 2；

height[6] 等于 1 < 2，temp ++ ， temp = 3；

height[7] 等于 3 >= 2，sum += temp = 5，temp = 0；

height[8] 等于 2 >= 2，sum += temp = 5，temp = 0；

height[9] 等于 1 < 2，temp ++ ，temp = 1；

height[10] 等于 2 >= 2，ans += temp = 6，temp = 0；

height[11] 等于 1 < 2，temp ++ = 1；

此时结束第二轮循环，sum = 6；

 再求第三行的水，看图就可以得出 只有height[7] = 3,此时开始更新temp；但是后边没有 height 大于等于 3 了，所以 sum 没有更新；所以最终的 sum 就是 6。

现在我们看看代码实现吧：

 public int trap(int[] height) {
        int sum = 0;
        int max = getMax(height);
        for (int i = 1; i <= max; i++) {
            boolean isStart = false; // 为true时,表示开始更新
            int temp = 0;
            for (int j = 0; j < height.length; j++) {
                if (height[j] < i && isStart) temp ++;
                if (height[j] >= i){
                    sum += temp;
                    temp = 0;
                    isStart = true;
                }
            }
        }
        return sum;
    }
    //用来计算最大高度
    public int getMax(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            Math.max(height[i], max);
        }
        return max;
    }

这种暴力解法时间很长，容易不能ac，时间复杂度为O(m*n),空间复杂度O(1);

因为计算时间受行数n和最大高度m影响，所以当最大高度越大，耗费时间越长。

2.按列计算

 思路：按列求就是从第一列到最后一列，把每一列的水单位加起来

如图，根据木桶效应，我们可以发现一个数学规律，每一列的水就取决于(左边最高的墙和右边最高的墙中较矮的墙）最矮的墙

我们可以分为二种情况：

1.较矮的墙高度大于当前的墙高度

此时当前列的水 = Math.min(左边最高的墙，右边最高的墙）- 当前列的墙

2.较矮的墙高度低于或者等于当前列的高度

 此时明显当前列是无水的。

分析了这三种情况，就很好理解了，只需求出每一列的左边最高的墙，右边最高的墙，找出较矮的墙就可以计算出当前列的水。

现在我们也看看代码实现把：

public int trap(int[] height) {
        int sum = 0;
        for (int i = 1; i < height.length; i++) {
            //求到左边最高的墙
            int left_max = 0;
            for (int j = i - 1; j >= 0; j--)
                left_max = Math.max(left_max, height[j]);

            //求到右边最高的墙
            int right_max = 0;
            for (int j = i + 1; j < height.length; j++)
                right_max = Math.max(right_max, height[j]);

            int min = Math.min(left_max, right_max);
            if (min > height[i]) sum += min - height[i];
        }
        return sum;
    }

这种解法的缺点也很明显就是耗费时间长，时间复杂度O(n^2)，当n越大，耗费时间越长；空间复杂度O(1);

3.用动态规划优化按列计算(空间换时间）

思路：第二种方法中我们计算左边最高的墙和右边最高的墙时，每次遍历都要进行重新计算，很浪费时间。

所以显而易见我们会想到用动态规划的方法进行优化，用两个数组，left_max[i] ，right_max[i]来存放每一列的左边最高墙的高度和右边最高墙的高度。

这边计算两个数组就有规律，计算left_max[i] 只需要用前一列的left_max[i-1] 和前一列的墙高度 进行比较就可得到，即 left_max[i] = Math.max(left_max[i-1] , height[i-1])

计算right_max[i] 只需要用后一列的right_max[i-1] 和后一列的墙高度 进行比较就可得到，即

right_max[i] = Math.max(right_max(i+1) , height[i+1]);

代码如下：

public int trap(int[] height) {
        int sum = 0;
        int[] left_max = new int[height.length];
        int[] right_max = new int[height.length];
        //求左边最高的墙的数组
        for (int i = 1; i < height.length; i++)
            left_max[i] = Math.max(left_max[i - 1], height[i - 1]);
        //求右边最高的墙的数组
        for (int i = height.length - 2; i > 0; i--)
            right_max[i] = Math.max(right_max[i + 1], height[i + 1]);

        for (int i = 1; i < height.length; i++) {
            int min = Math.min(left_max[i], right_max[i]);
            if (min > height[i]) sum += min - height[i];
        }
        return sum;
    }

这种方法就牺牲了一定的空间来换取时间，时间复杂度O(n)，空间复杂度O(n)。

4.双指针优化动态规划

动态规划时我们常常可以对空间复杂度进行进一步优化。

思路：就像这道题，我们的left_max[i]、right_max[i]中的元素事实上都只使用了一次，所以我们就可以进行优化，用一个变量代替数组；首先我们观察可以发现left_max[i]数组的遍历是和计算水同步的，我们就可以先对 left_max[i] 进行优化。

 public int trap(int[] height){
        int sum = 0 , left_max = 0;
        int[] right_max = new int[height.length];
        for (int i = height.length-2; i > 0 ; i--)
            right_max[i] = Math.max(right_max[i+1],height[i+1]);

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

我们可以把left_max数组去掉，但是我们不能以这种方式把right_max数组去掉，因为他们的遍历方式一个从左到右，一个从右到左。

所以我们就需要用到两个指针 left 和 right 来取代原先的 i；

那我们什么时候移动left指针，什么时候移动right指针呢？

首先我们知道我们为什么需要left_max和right_max指针，是为了得到较矮的墙的高度，从而计算水的单位数；所以只要当height[left-1]<height[right+1]时，left_max也小于right_max，就得知左边的墙是较矮的墙，向右移动left指针；同理相反时，右边的墙是较矮的墙，向左移动right指针。

初始值我们设置 left = 1 、right = height.length-2 ，当height [left-1] < height [right + 1] 时，左边的墙为最矮的墙，再计算水的单位数；相反同理。

public int trap(int[] height) {
        int left_max = 0,right_max = 0,sum = 0;
        int left = 1,right = height.length -2;
        for (int i = 1; i < height.length-1; i++) {
            if (height[left - 1] < height[right + 1]){
                left_max = Math.max(left_max,height[i-1]);
                int min = left_max; //这就是较矮的墙
                if (min > height[left]) sum += min - height[left];
                left ++; // 移动左指针
            }else {
                right_max = Math.max(right_max,height[right+1]);
                int min = right_max;
                if (min > height[right]) sum += min - height[right];
                right --; //移动右指针
            }
        }

        return sum;
    }

这种方法就既优化了时间复杂度，又节省了空间；

时间复杂度O(n),空间复杂度O(1)。

5.单调栈

 想到栈我们就会想到括号匹配，其实这道题也可以理解为括号匹配，只是更为复杂。

当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。

如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。

总体的原则就是，

当前高度小于等于栈顶高度，入栈，指针后移。

当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。

我们看具体的例子。

1.首先将 height [ 0 ] 入栈。然后 current 指向的高度大于栈顶高度，所以把栈顶 height [ 0 ] 出栈，然后栈空了，再把 height [ 1 ] 入栈。current 后移。

2.然后 current 指向的高度小于栈顶高度，height [ 2 ] 入栈，current 后移。

3.然后 current 指向的高度大于栈顶高度，栈顶 height [ 2 ] 出栈。计算 height [ 3 ] 和新的栈顶之间的水;计算完之后继续判断 current 和新的栈顶的关系。

4.current 指向的高度大于栈顶高度，栈顶 height [ 1 ] 出栈，栈空。所以把 height [ 3 ] 入栈。currtent 后移。

5.然后 current 指向的高度小于栈顶 height [ 3 ] 的高度，height [ 4 ] 入栈。current 后移。

6.然后 current 指向的高度小于栈顶 height [ 4 ] 的高度，height [ 5 ] 入栈。current 后移。

7.然后 current 指向的高度大于栈顶 height [ 5 ] 的高度，将栈顶 height [ 5 ] 出栈，然后计算 current 指向的墙和新栈顶 height [ 4 ] 之间的水。计算完之后继续判断 current 的指向和新栈顶的关系。此时 height [ 6 ] 不大于栈顶 height [ 4 ] ，所以将 height [ 6 ] 入栈。current 后移。

8.然后 current 指向的高度大于栈顶高度，将栈顶 height [ 6 ] 出栈。计算和新的栈顶 height [ 4 ] 组成两个边界中的水。然后判断 current 和新的栈顶 height [ 4 ] 的关系，依旧是大于，所以把 height [ 4 ] 出栈。计算 current 和 新的栈顶 height [ 3 ] 之间的水。然后判断 current 和新的栈顶 height [ 3 ] 的关系，依旧是大于，所以把 height [ 3 ] 出栈，栈空。将 current 指向的 height [ 7 ] 入栈。current 后移。

其实不停的出栈，可以看做是在找与 7 匹配的墙，也就是 3 。

而对于计算 current 指向墙和新的栈顶之间的水，根据图的关系，我们可以直接把这两个墙当做之前解法三的 left_max 和 right_max，然后之前弹出的栈顶当做每次遍历的 height [ i ]。水量就是 Min ( left_max ， right_max ) - height [ i ]，只不过这里需要乘上两个墙之间的距离。

可以看下代码继续理解下：

public int trap(int[] height){
        int sum = 0,current = 0; //current表示当前墙的位置
        Stack<Integer> stack = new Stack<>();
       while (current < height.length){
           while (!stack.isEmpty() && height[stack.peek()] < height[current]){
               int pop = height[stack.pop()]; //记录弹出的这个元素
               if (stack.isEmpty()) break; //如果当前栈无元素了，退出循环
               int distance = current - stack.peek() - 1; //两堵墙之间的距离
               int min = Math.min(height[current],height[stack.peek()]);
               sum += distance * (min - pop);
           }
           stack.push(current);
           current ++;
       }
        return sum;
    }

虽然while循环里面嵌套了一个while循环，但是由于一个元素最多被访问两次，入栈一次，出栈一次，所以时间复杂度：O(n)；

空间复杂度：O(n)，栈的空间

总结：

从方法二到方法三，利用动态规划，进行空间换时间；从方法三到方法四，利用双指针，又优化了动态规划所占有的空间；最后方法五，拓展了单调栈的解题方法。