给定 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 个单位的雨水(蓝色部分表示雨水)。
class Solution {
public int trap(int[] height) {
int n = height.length;
int lmax = 0, rmax = 0;
int l = 0, r = n - 1;
int ans = 0;
// 使用双指针法,移动左右指针,计算能够接的雨水量
while(l < r) {
if(height[l] < height[r]) {
// 左侧高度较小,判断当前位置能否接雨水
if(height[l] >= lmax) {
lmax = height[l]; // 更新左侧最大高度
} else {
ans += (lmax - height[l]); // 计算当前位置能接的雨水量
}
l++; // 左指针右移
} else {
// 右侧高度较小,判断当前位置能否接雨水
if(height[r] >= rmax) {
rmax = height[r]; // 更新右侧最大高度
} else {
ans += (rmax - height[r]); // 计算当前位置能接的雨水量
}
r--; // 右指针左移
}
}
return ans;
}
}
怎么能想到这个方法,这种双指针法的思路通常需要具备对问题的一定直觉和灵活性。尝试从两个方向靠拢,同时记录下某种状态(比如左右两侧的最大高度)是这种问题常见的思路。练习和熟悉这类问题,逐渐就能形成一种思维模式,能够更快地发现这类问题的解决方法