面试热题（接雨水问题）

青旅半醒 2023-10-14 12:40 24阅读 0赞

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

![0f031ddf0f5947dc8e473f0447031442.png][]

我们看到题的第一步，永远是对入参进行判断

public int trap(int[] height) {
            if (height == null) {
                return 0;
            }
              ...
        }

但是我们想想看，接雨水是不是和往桶里倒水的问题很像，倒入水的体积往往是由桶两边较低的那个高度决定的，这个问题亦是如此

![175dd6b9e34f46cfa11ca6223fe724e2.png][]![621bb2f957a147a5adb843b93f1e8bd0.png][]![53ffc1fb77a24e04897c3db839417079.png][]

由我们分析可知当数组的长度小于3的时候，是不可能接到雨水的，所以我们在判断入参条件的时候就可以这样写

public int trap(int[] height) {
            if (height == null || height.length < 3) {
                return 0;
            }
             ...
        }

刚才我们已经分析过了，一个位置的存储量只和最短的那一边有关系，边越长，我们固定位置上的存储量就越多，所以我们可以遍历每个位置，分别计算出各个位置上的存储量，再最后求和就完美的解决了本题

int count = 0;
            for (int i = 1; i < height.length; i++) {
                //找左边的最高值
                int lMax = 0;
                for (int j = 0; j < i; j++) {
                    lMax = Math.max(lMax, height[j]);
                }
                //找到右边的最高值
                int rMax = 0;
                for (int j = i + 1; j < height.length; j++) {
                    rMax = Math.max(rMax, height[j]);
                }
               }

好了，这样我们相对位置上的两边最高的边已经求出来了，只不过现在还存一个问题，如果，当前位置的高度如果大于较小的那边高度的话，是否还可有存储水量呢？

![e5f7168b1de94efaaa47e22e7ba0c4c8.png][]

所以当前位置的高度如果大于两边最长的相对较小的边的高度，则不能进行存储水量，所以我们再对我们的代码进行完善

这就完成了我们所谓hard题的接雨水问题了，这个题面试中还是经常问的，希望大家透析原理，面试无压力，下面给大家奉上整个代码，供大家参考借鉴

public int trap(int[] height) {
            if (height == null || height.length < 3) {
                return 0;
            }
            int count = 0;
            for (int i = 1; i < height.length; i++) {
                //找左边的最高值
                int lMax = 0;
                for (int j = 0; j < i; j++) {
                    lMax = Math.max(lMax, height[j]);
                }
                //找到右边的最高值
                int rMax = 0;
                for (int j = i + 1; j < height.length; j++) {
                    rMax = Math.max(rMax, height[j]);
                }
                if (Math.min(lMax, rMax) - height[i] > 0) {
                    count += Math.min(lMax, rMax) - height[i];
                }
            }
            return count;
        }

![6f98ae6a96674d4e9aac9cf0f33d0c92.png][]

这种解法由于太暴力了，面试官肯定不想看到这种比较笨的办法，下面给大家介绍一种比较容易理解的双指针

说是双指针也不是真正意义上的双指针，它是分别维护了一个当前的左右指针，还有左右的最高指针

*  因为最左边的和最右边的肯定是不能装水，所以我们把这两个设为左右最高，那么当前的左右指针就会从1~n-2开始

int len = height.length;
            int left = 1;
            int right = len - 2;
            int left_max = 0;
            int right_max = len - 1;

*  当左边的最高小于右边的最高，就说明当前的值的存水量只与左边的最高有关系，如果左边的最高 大于当前值，那么当前位置的存水量一定是

res += height[left_max] - height[left];

*  如果左边的最高值小于当前位置的高度，说明原来的最高不是真的最高，然后对最高进行更新

left_max = left;

*  然后继续向后比较下一个位置

left++;

左边的代码如下：

if(height[left_max] < height[right_max]){
                    if(height[left_max] > height[left]){
                        res += height[left_max] - height[left];
                    }else{
                        left_max = left;
                    }
                    left++;}

右边的比较方法和左边的方法一致，这里就直接给出代码：

if(height[left_max] >= height[right_max]){
                     if(height[right_max] > height[right]){
                        res += height[right_max] - height[right];
                    }else{
                        right_max = right;
                    }
                    right--;}

然后将两者进行合并就可以得出最后的结果

public int trap(int[] height) {
            //获取数组的长度
            int len = height.length;
            //当前左
            int left = 1;
            //当前右
            int right = len - 2;
            //左最高
            int left_max = 0;
            //右最高
            int right_max = len - 1;
    
            int res = 0;
    
            while(left <= right){
                //比较
                if(height[left_max] < height[right_max]){
                    if(height[left_max] > height[left]){
                        res += height[left_max] - height[left];
                    }else{
                        left_max = left;
                    }
                    left++;
                }else{
                    if(height[right_max] > height[right]){
                        res += height[right_max] - height[right];
                    }else{
                        right_max = right;
                    }
                    right--;
                }    
            }
            return res;
        }

![1419259d9c2b48f2939cd55a50227726.png][]

下面再介绍一种按照不同的双指针思想求解问题

*  对于某一个位置的i来说，我们能否接到这个位置上的雨水，取决于i左右两侧的最大值（left\_max,right\_max）是否比height\[i\]大，只有当i左右两侧的最大值都比height\[i\]大时，才能接i上的雨水，数量为min(left\_max,right\_max)-height\[i\]，可以得到结论：**限制当前位置接雨水的条件是其左右两侧的最大值中的较小值min(left\_max,right\_max);**
 *  对于left、right两个指针，left从左向右移动，right从右向左移动，对于left来说，left\_max是真实可信的，因为left\_max是left亲自走出来的，但是right\_max对于left却是不可信的，因为left不知道从height\[left\]到height\[right\]之间是否其他的数大于right\_max，同样，对于right来说，left\_max也是不可信的，所以这里可以得到结论：**对于左指针left，它右侧的真实的最大值>=right\_max,对于右指针right,它左侧的真实最大值>=left\_max**
 *  当left\_max<right\_max的时候，左指针的位置是否能接雨水就已经可以确定了，当left\_max<=right\_max的时候，右指针的位置是否能接雨水就已经可以确定了

public int trap(int[] height) {
            int len = height.length;
            int left = 0;
            int right = len - 1;
            int left_max = 0;
            int right_max = 0;
            int res = 0;
            //当left==right的时候，他们两指向的一定是数组中最大的那个数，是不能进行解雨水的，所以
            //这里left<right也可以ac
            while(left <= right){
                left_max=Math.max(left_max,height[left]);
                right_max=Math.max(right_max,height[right]);
               if(left_max<right_max){
                   res+=left_max-height[left];
                   left++;
               }else{
                   res+=right_max-height[right];
                   right--;
               }
            }
            return res;
        }

![0b286b3979dd48baa85deb79b5598a36.png][]

[0f031ddf0f5947dc8e473f0447031442.png]: https://img-blog.csdnimg.cn/0f031ddf0f5947dc8e473f0447031442.png
[175dd6b9e34f46cfa11ca6223fe724e2.png]: https://img-blog.csdnimg.cn/175dd6b9e34f46cfa11ca6223fe724e2.png
[621bb2f957a147a5adb843b93f1e8bd0.png]: https://img-blog.csdnimg.cn/621bb2f957a147a5adb843b93f1e8bd0.png
[53ffc1fb77a24e04897c3db839417079.png]: https://img-blog.csdnimg.cn/53ffc1fb77a24e04897c3db839417079.png
[e5f7168b1de94efaaa47e22e7ba0c4c8.png]: https://img-blog.csdnimg.cn/e5f7168b1de94efaaa47e22e7ba0c4c8.png
[6f98ae6a96674d4e9aac9cf0f33d0c92.png]: https://img-blog.csdnimg.cn/6f98ae6a96674d4e9aac9cf0f33d0c92.png
[1419259d9c2b48f2939cd55a50227726.png]: https://img-blog.csdnimg.cn/1419259d9c2b48f2939cd55a50227726.png
[0b286b3979dd48baa85deb79b5598a36.png]: https://img-blog.csdnimg.cn/0b286b3979dd48baa85deb79b5598a36.png