接雨水

发表于 分类于 ， ， 阅读次数：

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

力扣图片

1
2
3
输入：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 个单位的雨水（蓝色部分表示雨水）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int trap(int[] height) {
        int len=height.length;
        int i=0,j=len-1,k=1;
        int sum=0;
        while(i<j)
        {

            if(height[i]>=k&&height[j]>=k)
            {
                for(int x=i+1;x<j;x++)
                {
                    if(height[x]<k)
                    {
                        sum++;
                    }
                }
                k++;
                i=0;
                j=len-1;
            }
            else if(height[i]>=k)
            {
                j--;
            }
            else if(height[j]>=k)
            {
                i++;
            }
            else
            {
                j--;
                i++;
            }
        }
        return sum;
    }
}

本题我的做法主要思想还是双指针，分别将双指针放在数组的最左边和最右边，观察图形可以一层一层的来看，先找到两端第一个大于等于1的方块，则在第一层这两个方块之间低于1的部分可以储存一份水，然后再看第二层（让k变成2），找到两端第一个大于等于2的方块，则在第二层这两个方块之间低于2的部分可以储存一份水(只记第二层的水，因为第一层已经记录了)。最后以此类推，直到两端找不到同时大于某个高度的数为止。

运行结果

执行用时：2739 ms, 在所有 Java 提交中击败了5.01%的用户

内存消耗：43.6 MB, 在所有 Java 提交中击败了5.02%的用户

通过测试用例：322 / 322

大神题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int trap(int[] walls) {
        if (walls == null || walls.length <= 2) {
            return 0;
        }

        // 思路：
        // 单调不增栈，walls元素作为右墙依次入栈
        // 出现入栈元素（右墙）比栈顶大时，说明在右墙左侧形成了低洼处，低洼处出栈并结算该低洼处能接的雨水

        int water = 0;
        Stack<Integer> stack = new Stack<>();
        for (int right=0; right<walls.length; right++) {
            // 栈不为空，且当前元素（右墙）比栈顶（右墙的左侧）大：说明形成低洼处了
            while (!stack.isEmpty() && walls[right]>walls[stack.peek()]) {
                // 低洼处弹出，尝试结算此低洼处能积攒的雨水

                int bottom = stack.pop();

                // 看看栈里还有没有东西（左墙是否存在）
                // 有右墙+有低洼+没有左墙=白搭
                if (stack.isEmpty()) {
                    break;
                }

                // 左墙位置以及左墙、右墙、低洼处的高度
                int left = stack.peek();
                int leftHeight = walls[left];
                int rightHeight = walls[right];
                int bottomHeight = walls[bottom];

                // 能积攒的水=(右墙位置-左墙位置-1) * (min(右墙高度, 左墙高度)-低洼处高度)
                water += (right-left-1) * (Math.min(leftHeight, rightHeight)-bottomHeight);
            }

            // 上面的pop循环结束后再push，保证stack是单调不增
            stack.push(right);

        }

        return water;
    }
}

https://leetcode.cn/problems/trapping-rain-water/solution/trapping-rain-water-by-ikaruga/

引用自此评论区

该方法运用了栈的思想，先找到左边比右边矮的地方,于是此时栈的顶部就是凹陷地方，right就是右墙，再把栈顶元素取出，如果栈剩下的为空，则没有左墙直接跳出，如果有，假如凹陷的地方取出栈后，此时的栈左墙是和凹陷的地方一样高的（不可能比凹陷的地方矮，程序试从左到右找凹陷的），则由于water += (right-left-1) * (Math.min(leftHeight, rightHeight)-bottomHeight);此时的水深度仍然算出来记录为零，由于while循环的存在，此时凹陷处会向左移动（栈顶元素取出了凹陷向左移动），直到找出左墙比凹陷高，此时就可以算出凹陷的水的格数了。但这种做法时间效率没有比我的做法效率提升多少，下面还有一种方法效率最好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int trap(int[] height) {
        // int left=0,right=height.length-1;
        // int maxL=height[left],maxR=height[right];
        // int res=0;
        // while(left<right){
        //     maxL=Math.max(maxL,height[left]);
        //     maxR=Math.max(maxR,height[right]);
        //     res+=maxR>maxL?maxL-height[left++]:maxR-height[right--];
        // }
        // return res;
        int sum=0;

        int index=0;
        for(int i=0;i<height.length;i++){
            if(height[i]>height[index]){
                index=i;
            }
        }
        int left=0;
        for(int i=1;i<index;i++){
            if(height[i]<height[left]){
                sum+=height[left]-height[i];
            }else if(height[i]>=height[left]){
                left=i;
            }
        }

        int right=height.length-1;
        for(int i=height.length-2;i>index;i--){
            if(height[i]<height[right]){
                sum+=height[right]-height[i];
            }else if(height[i]>=height[right]){
                right=i;
            }
        }
        return sum;
    }
}

来自提交答案时官方的标准解答

此方法是先找出图像的最高点，然后由此分成左右两个部分，这样每一列水的格数就取决于两边短板的高度了，小于短板高度就可以存储雨水，最后加起来，此算法我觉得很简单，效率也表现出来了最优。