【LeetCode】☂☂☂接雨水Ⅰ、Ⅱ（多种方法求解）

喜欢ヅ旅行 2023-01-05 01:19 144阅读 0赞

## 【LeetCode】☂☂☂接雨水Ⅰ、Ⅱ ##

### 接雨水★★★ ###

[LeetCode42. 接雨水][LeetCode42.]

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

【**示例**】

![在这里插入图片描述][20210111111848244.png_pic_center]

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

【**解题思路**】由图可知，对于一个位置而言，若它左右都有比它高的柱体，则可以接到雨水。

怎样判断接到多少雨水呢？与`木桶原理`类似，就是取左边最大值与右边最大值中的最小值，与当前柱体高度做差就是其面积

更新结果为 `rain += Math.max(0, Math.min(leftMax, rightMax) - height[i])`

#### 方法一：暴力法 ####

对于每一个柱体，暴力查找左右两边的最大值

时间复杂度为`O(n²)`

class Solution {
        
        public int trap(int[] height) {
        
            if(height == null || height.length < 3) return 0;
            int N = height.length;
            int rain = 0;
            for(int i = 1; i < N - 1; i++) {
        
                int leftMax = 0, rightMax = 0;
                for(int j = 0; j < i; j++) {
           
                    leftMax = Math.max(leftMax, height[j]);
                }
                for(int j = i + 1; j < N; j++) {
        
                    rightMax = Math.max(rightMax, height[j]);
                }
                rain += Math.max(0, Math.min(leftMax, rightMax) - height[i]);
            }
            return rain;
        }
    }

#### 方法二：空间换时间 ####

利用两个数组分别保存左边最大值和右边最大值，

时间复杂度为`O(n)`，空间复杂度为`O(n)`

class Solution {
        
        public int trap(int[] height) {
        
            if(height == null || height.length < 3) return 0;
            int N = height.length;
            int[] leftMaxs  = new int[N];
            int[] rightMaxs = new int[N];
            
            leftMaxs[0] = height[0];
            rightMaxs[N - 1] = height[N - 1];
            for(int i = 1; i < N; i++) {
        
                leftMaxs[i] = Math.max(leftMaxs[i - 1], height[i]);
            }
            for(int i = N - 2; i >= 0; i--) {
        
                rightMaxs[i] = Math.max(rightMaxs[i + 1], height[i]);
            }
    
            int rain = 0;
            for(int i = 1; i < N - 1; i++) {
        
                rain += Math.max(0, Math.min(leftMaxs[i - 1], rightMaxs[i + 1]) - height[i]);
            }
            return rain;
        }
    }

#### 方法三：双指针法 ####

先初始化左边最大值为第一个元素，右边最大值为最后一个元素

双指针`L, R`遍历`[1, n - 2]`

*  若左边最大值小于右边最大值，则左边值为下标`L`处的短板，更新`rain`和左边最大值，并将`L++`
 *  相反，右边最大值小于左边最大值，则右边值为下标`R`处的短板，更新`rain`和右边最大值，并将`R--`

时间复杂度`O(n)`，空间复杂度`O(1)`

class Solution {
        
        public int trap(int[] height) {
        
            if(height == null || height.length < 3) return 0;
            int L = 1, R = height.length - 2;
            int leftMax = height[0], rightMax = height[height.length - 1];
            int rain = 0;
            while(L <= R) {
        
                if(leftMax < rightMax) {
        
                    rain += Math.max(0, leftMax - height[L]);
                    leftMax = Math.max(leftMax, height[L++]);
                }else {
        
                    rain += Math.max(0, rightMax - height[R]);
                    rightMax = Math.max(rightMax, height[R--]);
                }
            }
            return rain;
        }
    }

#### 方法四：单调栈 ####

[参考甜姨（sweetie）题解][sweetie]

class Solution {
        
        public int trap(int[] height) {
        
            if(height == null || height.length < 3) return 0;
            int rain = 0;
            Stack<Integer> stack = new Stack<Integer>();
            for(int i = 0; i < height.length; i++) {
        
                while(!stack.isEmpty() && height[stack.peek()] < height[i]) {
        
                    int curId = stack.pop();
                    //将高度与height[curId]相同的出栈
                    while(!stack.isEmpty() && height[stack.peek()] == height[curId]) {
        
                        stack.pop();
                    }
                    if(!stack.isEmpty()) {
        
                        int topId = stack.peek();
                        //可接雨水深度
                        int deep = Math.min(height[topId], height[i]) - height[curId];
                        // (i - topId - 1) 为宽度
                        rain += deep * (i - topId - 1);
                    }
                }
                stack.push(i);
            }
            return rain;
        }
    }

--------------------

### 接雨水Ⅱ★★★ ###

[LeetCode407. 接雨水 II][LeetCode407. _ II]

【**题目**】给你一个 `m x n` 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

【**示例**】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

给出如下 3x6 的高度图:
    [
      [1,4,3,1,3,2],
      [3,2,1,3,2,4],
      [2,3,3,2,3,1]
    ]
    返回 4 。

【**解题思路**】优先队列

此题不能考虑上下左右四个方向，而是要考虑周围一圈，翻车后才知道的—

[参考Jerry题解<优先队列的思路解决接雨水II，逐行解释>链接][Jerry_II]

*  构建最小堆，初始化堆为矩阵的最外围（最外面一圈）
 *  不断出队，若堆顶元素（四周元素中最矮的一个）大于四周要遍历的元素，堆顶元素减去当前要遍历的元素值即为可接雨水的量
 *  接完雨水后要将当前遍历元素入队，注意高度要更新为接完雨水后的高度；接不到也要取最大值

class Solution {
        
        public int trapRainWater(int[][] heightMap) {
        
            if(heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) {
        
                return 0;
            }
            int m = heightMap.length, n = heightMap[0].length;
            //标记数组有没有访问过
            boolean[][] visted = new boolean[m][n];
            //队列中加入的是三元组[x, y, h], 坐标和高度, 根据高度由低到高排序
            PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1, o2) -> o1[2] - o2[2]);
    
            //将最外一圈入队
            for(int i = 0; i < m; i++) {
        
                for(int j = 0; j < n; j++) {
        
                    if(i == 0 || j == 0 || i == m - 1 || j == n - 1) {
        
                        queue.offer(new int[]{
        i, j, heightMap[i][j]});
                        visted[i][j] = true;
                    }
                }
            }
    
            int rain = 0;
            //方向数组，把dx和dy压缩成一维
            int[] dirs = {
        -1, 0, 1, 0, -1};
            while(!queue.isEmpty()) {
        
                int[] min = queue.poll();
                //看一下周围四个方向，没访问过的话能不能往里面灌水
                for(int i = 0; i < dirs.length - 1; i++) {
        
                    int x = min[0] + dirs[i];
                    int y = min[1] + dirs[i + 1];
                    //如果位置合法且没有被访问过
                    if(x >= 0 && x < m && y >= 0 && y < n && !visted[x][y]) {
        
                        //如果最外围最小元素比当前元素还高，则可以接到雨水
                        if(min[2] > heightMap[x][y]) rain += min[2] - heightMap[x][y];
                        //如果灌水了高度得取灌水后的高度，如果没灌水也要取高的
                        queue.offer(new int[]{
        x, y, Math.max(min[2], heightMap[x][y])});
                        visted[x][y] = true;
                    }
                }
            }
    
            return rain;
        }
    }

[LeetCode42.]: https://leetcode-cn.com/problems/trapping-rain-water/
[20210111111848244.png_pic_center]: /images/20221119/0ff1f965048747138bdd5121b85a7fe3.png
[sweetie]: https://leetcode-cn.com/problems/trapping-rain-water/solution/dan-diao-zhan-jie-jue-jie-yu-shui-wen-ti-by-sweeti/
[LeetCode407. _ II]: https://leetcode-cn.com/problems/trapping-rain-water-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210111111914886.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw==,size_16,color_FFFFFF,t_70#pic_center
[Jerry_II]: https://leetcode-cn.com/problems/trapping-rain-water-ii/solution/you-xian-dui-lie-de-si-lu-jie-jue-jie-yu-shui-ii-b/