问题

42.诱捕雨水

类型：硬
喜欢： 29k
不喜欢： 412

问这个问题的公司
公司：没有时间问

亚马逊14
彭博5
Adobe 4
苹果4
高盛3
Yandex 3
EPAM系统2
微软16
Google 9
Uber 4
makemytrip 3
Facebook 2
eBay 2
Salesforce 2
英特尔8
Rubrik 8
Qualtrics 7
特斯拉6
Oracle 5
城堡5
VMware 4
C3物联网4
Snapchat 3
提起3
签证3
贝宝3
ServiceNow 3
Swiggy 3
国家乐器3
智慧3
Zoho 2
Intuit 2
Coupang 2
雅虎2
Expedia 2
Twitch 2
摩根士丹利2
肖2
Teltok 2
navi 2
Airbnb 1
zenefits 1
Twitter 1
Wix 1

给定n个非阴性整数，代表一个高程图，其中每个条的宽度为1，计算下雨后可以捕获多少水。

示例1：
输入：高度= [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

说明：上面的高程图（黑色部分）由阵列[0,1,0,2,1,0,1,3,2,2,1,2,1]表示。在这种情况下，将被困6个雨水（蓝色部分）。

示例2：
输入：高度= [4,2,0,3,2,5]
输出：9

约束：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

直觉：

目的是计算给定高度的杆之间的总被困水。我们通过计算每个条的左右边界来实现这一目标，然后根据这些边界计算被困的水。

方法：

• 初始化为0，LB（左边界）和RB（右边界）数组。
• 计算输入阵列中每个栏的左边界（LB）和右边界（RB）。
• 通过输入阵列进行迭代，计算每个条的被困水，然后在Res中堆积。
• 返回res作为被困的水。

复杂：

时间复杂性： o（n），其中n是输入阵列中的元素数量。

空间复杂性： o（n），由于LB和RB阵列用于存储边界。

代码：

class Solution {
    public int trap(int[] height) {
        int  res = 0;
        int[] lb = new int[height.length];
        int[] rb = new int[height.length];

        lb[0] = height[0];
        for(int i = 1 ; i < height.length -1 ;i++){
            lb[i] = Math.max(height[i],lb[i-1]);
        }

        rb[height.length - 1] = height[height.length - 1 ];
        for(int i = height.length - 2 ; i >= 0;i--){
            rb[i] = Math.max(height[i],rb[i+1]);
        }

        for(int i = 1 ; i < height.length -1 ; i++){
            int tw = Math.min(lb[i],rb[i]) - height[i];
            res = res + tw;
        }

        return res;
    }
}

愉快的编码，
湿婆