数据结构和算法【46】接雨水

皮皮克克 2023-09-15

点击关注公众号，干货第一时间送达

这道题小编很早之前做过了，

不过一直没来得及更。

今天应朋友之邀，更了这题。

很经典的一道题，

一起来看看。

没错，就是大名鼎鼎的 "接雨水"，

接雨水还有另外一个版本，是三维空间的：

后面这道大家有兴趣可以先自己看看，

今天咱们先聊聊第一题。

一、屏幕前的吴彦祖和刘亦菲们，请听题

举个例子：

height = [0,1,0,2,1,0,1,3,2,1,2,1]

题意简单，一目了然。

怎么求解呢？

二、解题

对于给定柱子数组

height = [0,1,0,2,1,0,1,3,2,1,2,1]

怎么能接到雨水？

那必须是当前的柱子 height[i] 左右两边的柱子等于或高于它，

但是，如果我们关注某个柱子的近邻左右两侧，

是不好解题的。

我们应该关注当前柱子，左右两边界，

我们可以发现，只有左右边界能够挡住水，

也就是当前柱子低于左右边界，

不管其他柱子，水一定能够保留下来。

而我们每次只计算当前柱子，上面的地方可以保存多少水：

其他柱子不用管，因为在遍历中，后面会遍历到，

比如：

看看代码。

完整代码：

public class CodingDemo {

    /**
     * TODO; 接雨水
     * @param height
     * @return
     */
    private static int trap(int[] height) {
        if (height == null || height.length == 0){
            return 0;
        }

        int N = height.length;

        //记录左右两边最大值
        int maxLeft = height[0];
        int maxRight = height[N-1];

        //指针
        int left = 1;
        int right = N-2;

        //接到的雨水
        int all = 0;

        while (left <= right){
            if (maxLeft < maxRight){
                int cur = maxLeft - height[left];
                int rain = Math.max(cur, 0);
                all += rain;

                //更新左边界
                maxLeft = Math.max(maxLeft, height[left]);
                left++;
            } else {
                int cur = maxRight - height[right];
                int rain = Math.max(cur, 0);
                all += rain;

                //更新右边界
                maxRight = Math.max(maxRight, height[right]);
                right--;
            }
        }
        return all;
    }


    public static void main(String[] args) {

        int[] arr = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(arr));
    }
}