算法图解——截留雨水( Trapping Rain Water)

1. 题目描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

为了方便理解,还是决定给大家翻译一下吧:

给定n个非负整数,表示一个高度图,其中每个条形的宽度为1,计算从上往下下雨后它能集聚多少水。

2. 示例

示例1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

什么意思呢?通过一个图我们就明白了,大概是这样:

算法图解——截留雨水( Trapping Rain Water)

 

 

 图中黑色的表示高度数组值,蓝色的表示集聚的雨水,一个方格代表1,故集聚了6个单位的雨水。

示例2:

同理:

Input: height = [4,2,0,3,2,5]
Output: 9

图示这样:黄色为高度值,蓝色为雨水量。

算法图解——截留雨水( Trapping Rain Water)

 

 

 

3. 输入要求

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105
  • 复杂度要求为O(n)

 

4. 题目解析

有人看到示例2会觉得,咦?是不是可以用面积来计算呢?

但是又看到示例1的时候,会发现,面积并不是特别方便,因为,并不是中间所有的间隙都能够储存雨水。只有形成“凹”字型时,才能够集聚雨水。

所以我们只能另辟蹊径。

我们使用多指针法:假设数组为A[length];

因为要求复杂度为O(N),故需要遍历一遍,故分别设置 left 和 right 两个指针。并使用while(left<right)来控制循环。

 其实,我们从示例1中这张图就可以看出:如果我们设置一个中间变量 Max 用来表示当前遇到的最大值,那么,在遍历高度数组A时,下一个数组值 A[left] 如果比 Max 小,则用Max减去该值就是此处可以存储的雨水量,且更新 left 继续遍历;如果该值 A[left] 大于 Max 时,那么 Max 更新为 A[left],且更新 left 指针,继续遍历。

代码如:

if(A[left]>=Max){
    Max = A[left];
}else{
    res += (Max-A[left]);
}
left++;

算法图解——截留雨水( Trapping Rain Water)

 

 

 但是,我们这里要考虑的不仅仅是一面,因为会存在这样一种情况就是:

输入为:[5,0,0,0,0,0]

输出不是5*5=25,而是0,因为右侧没有高度,形成不了“凹”字型。

所以我们应该还需要设置右侧最大值,为了与前面的最大值Max做区分,我们将前述的最大值 Max 改为 leftMax,此处右侧最大高度值为rightMax,这样我们就可以从两侧向中间收缩。

判断到底当前步是从左还是从右收缩,需要依据 A[left] 和 A[right] 的值的大小——【谁小谁收缩】

右侧代码为:

if(A[right]>=rightMax){
    rightMax = A[right];
}else{
    res += (Max-A[right]);
}
right--;

故:整体过程就是:

public  int trap(int[] A){
    int res = 0;
    int left = 0;
    int right = A.length-1;
    int leftMax = 0;  //左侧海拔最高值
    int rightMax = 0;   //右侧海拔最高值

    while(left<right){
        if(A[left]<=A[right]){     //左右两侧谁矮收缩谁
            if(A[left]>=leftMax){
                leftMax = A[left];   //更新左侧海拔最高值
            }else{
                res += (leftMax-A[left]);   //累计雨水量
            }
            left++;   //更新左侧指针
        }else{
            if(A[right]>=rightMax){
                rightMax = A[right];     //更新右侧海拔最高值
            }else{
                res += (rightMax-A[right]);    //累计雨水量
            }
            right--;     //更新右侧指针
        }
    }
}

 

 

参考及致谢:

1、LeetCode Top 100 高频算法题42. Trapping Rain Water:来自《菜鸟名企梦》公众号,希望大家关注一波,谢谢~~~

算法图解——截留雨水( Trapping Rain Water)

 

 

 

 

Over...

 

算法图解——截留雨水( Trapping Rain Water)

上一篇:nrf2401 - 最廉价的2.4G无线通信方案


下一篇:AcWing 1074. 二叉苹果树