大家好!我是曾续缘💌
今天是《LeetCode 热题 100》系列
发车第 7 天
双指针第 4 题
❤️点赞 👍 收藏 ⭐再看,养成习惯
接雨水 给定
n
个非负整数表示每个宽度为1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。示例 1:
输入: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
1 <= n <= 2 * 104
0 <= height[i] <= 105
解题方法
对于当前这一列能装多少水, 是由它左边最高的柱子和右边最高柱子共同决定的,
更具体点是有两者中最小的柱子决定的,当然还需要减去当前这一列的柱高.
我们使用l
,r
来表示左右两边遍历到的柱子, ml
,mr
表示左右两边目前遍历到的最高的柱子高度,(不是最高的不影响答案).
对于l
这一列来说, 能装多少水,是由它左边最高的柱子和右边最高柱子共同决定的,
其中ml
是已知的了, mr
只代表了目前r
位置往右的, 不代表l
位置右边的最高的柱子高度, 因此还不能求能装多少水. 但是如果知道了ml < mr
, 再根据mr
的定义可以推理出l
右边最高柱子肯定是大于当前的mr
,也就是间接知道了左边最高的柱子低于右边最高柱子,也就是知道了两者中最小的柱子(左柱子),因此可以求出当前l
这个位置装的水. 对于r
的位置分析,同理.
Code
class Solution {
public int trap(int[] height) {
int n = height.length, l = 0, r = n - 1, ml = 0, mr = 0;
int ans = 0;
while(l < r){
ml = Math.max(ml, height[l]);
mr = Math.max(mr, height[r]);
if(ml < mr){
ans += ml - height[l];
l++;
}else{
ans += mr - height[r];
r--;
}
}
return ans;
}
}