求解思路
这道题的关键在于理解每个位置能接多少水。
想象你站在某个位置i上，这个位置能接住的水量取决于什么呢?
其实就是左右两边的"围墙"能托住多高的水。
具体来说就是左右两边最高的柱子,其中，这两个高度中较矮的那个决定了水位线,然后用这个水位线减去当前位置的高度,就是这个位置能接的水量。
如果当前位置本身就比水位线高,那自然接不住水。
所以问题就转化成了:
对于每个位置,我们需要知道它左边的最大值和右边的最大值,然后取两者的较小值作为水位,最后累加每个位置能接的水量即可。
方法1
既然需要知道每个位置左右两边的最大值,最直接的想法就是提前算好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public static int trap(int[] nums) {
int n = nums.length;
int[] lmax = new int[n];
int[] rmax = new int[n];
// 计算每个位置左边的最大值
lmax[0] = nums[0];
for (int i = 1; i < n; i++) {
lmax[i] = Math.max(lmax[i - 1], nums[i]);
}
// 计算每个位置右边的最大值
rmax[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
rmax[i] = Math.max(rmax[i + 1], nums[i]);
}
// 累加每个位置能接的水量
int ans = 0;
for (int i = 1; i < n - 1; i++) {
ans += Math.max(0, Math.min(lmax[i - 1], rmax[i + 1]) - nums[i]);
}
return ans;
}
|
方法2
假设左边最大值小于等于右边最大值,那么左指针位置的接水量只取决于左边最大值,右边再高也没用。反之亦然。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static int trap(int[] nums) {
int l = 1, r = nums.length - 2;
int lmax = nums[0], rmax = nums[nums.length - 1];
int ans = 0;
while (l <= r) {
if (lmax <= rmax) {
// 左边矮,左指针位置的水量确定
ans += Math.max(0, lmax - nums[l]);
lmax = Math.max(lmax, nums[l++]);
} else {
// 右边矮,右指针位置的水量确定
ans += Math.max(0, rmax - nums[r]);
rmax = Math.max(rmax, nums[r--]);
}
}
return ans;
}
|
如果觉得有帮助，欢迎点赞、关注、转发~