LeetCode_双指针_困难_42.接雨水

小鱼儿 2023-10-06 18:54 21阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例1：**  
![在这里插入图片描述][8d9ea1c2cd514b2abcbbad0c545b893f.png]

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

**示例 2：**  
输入：height = \[4,2,0,3,2,5\]  
输出：9

**提示：**  
n == height.length  
0 <= n <= 3 \* 104  
0 <= height\[i\] <= 105

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

## 2.思路 ##

（1）暴力穷举法  
暴力穷举法的主要思想在于求出每个位置 i 能够接的雨水量，然后将其全部相加即可。而位置 i 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关，这里分别称这两个柱子高度为 leftMax 和 rightMax，那么位置 i 最大的水柱高度就是 min(leftMax, rightMax)，该位置可以接的雨水量为 `min(max(height[0...i]), max(height[i...end])) - height[i]`。

（2）双指针  
① 定义雨水量 res 以及分别指向数组首和数组尾的指针 left 和 right， 初始值分别为 0、0、height.length - 1。

② 维护所有位置左右两侧高度最高的柱子 leftMax 和 rightMax，对于某侧的柱子，若存在高度更高的柱子则可以舍弃，因此哪侧柱子高度底，就更新哪侧（它们的初始值均为 0）；

③ 当两指针没有相遇时，使用 height\[i\] 和 height\[j\] 分别来更新 leftMax 和 rightMax 的值；

*  **若 leftMax < rightMax**，计算下标 left 处能够接到的雨水量 leftMax - height\[left\]，并累加给 res，并且 left 向后移动一位；
 *  **若 leftMax ≥ rightMax**，计算下标 right 处能够接到的雨水量 rightMax - height\[right\]，并累加给 res，并且 right 向前移动一位；

④ 两指针相遇后，结束 while 循环，直接返回 res 即可。

相关题目：  
[LeetCode\_双指针\_中等\_11.盛最多水的容器][LeetCode_11.]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
    	public static int trap(int[] height) {
        
    	    int length = height.length;
    	    int res = 0;
    	    for (int i = 1; i < length - 1; i++) {
        
    	        int leftMax = 0, rightMax = 0;
    	        //寻找左边最高的柱子
    	        for (int j = i; j >= 0; j--) {
        
    	            leftMax = Math.max(leftMax, height[j]);
    	        }
    	        //寻找右边最高的柱子
    	        for (int j = i; j < length; j++) {
        
    	            rightMax = Math.max(rightMax, height[j]);
    	        }
    	        //计算当前位置 i 处能够接的雨水量
    	        res += Math.min(leftMax, rightMax) - height[i];
    	    }
    	    return res;
    	} 
    }

//思路2————双指针
    class Solution {
        
        public static int trap(int[] height) {
        
            int res = 0;
            // left 和 right 分别指向数组首和数组尾的指针
            int left = 0;
            int right = height.length - 1;
            // leftMax 和 rightMax 分别表示左右两侧柱子的最高高度，初始值均为 0
            int leftMax = 0;
            int rightMax = 0;
            while (left < right) {
        
                leftMax = Math.max(leftMax, height[left]);
                rightMax = Math.max(rightMax, height[right]);
                if (leftMax < rightMax) {
        
                    res += leftMax - height[left++];
                } else {
        
                    res += rightMax - height[right--];
                }
            }
            return res;
        }
    }

[8d9ea1c2cd514b2abcbbad0c545b893f.png]: https://img-blog.csdnimg.cn/8d9ea1c2cd514b2abcbbad0c545b893f.png
[LeetCode_11.]: https://blog.csdn.net/weixin_43004044/article/details/118070754