首先，碰到这样的题目不要慌张，挨个分析每个A[i]能trapped water的容量，然后将所有的A[i]的trapped water容量相加即可
其次，对于每个A[i]能trapped water的容量，取决于A[i]左右两边的高度（可延展）较小值与A[i]的差值，即volume[i] = [min(left[i], right[i]) - A[i]] * 1，这里的1是宽度，如果the width of each bar is 2,那就要乘以2了”
那么如何求A[i]的左右高度呢？ 要知道，能盛多少水主要看短板。那么对每个A[i]来说，要求一个最高的左短板，再求一个最高的右短板，这两个直接最短的板子减去A[i]原有的值就是能成多少水了。
所以需要两遍遍历，一个从左到右，找最高的左短板；一个从右到左，找最高的右短板。最后记录下盛水量的总值就是最终结果了。
有人可以用O(1)space 做 大概思路是看左右bottom neck, 要学习
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | public class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) return 0;
int leftHighest[] = new int[height.length];
int rightHighest[] = new int[height.length];
leftHighest[0] = height[0];
rightHighest[height.length-1] = height[height.length-1];
for (int i = 1, j = height.length-2; i < height.length; i++, j--){
leftHighest[i] = Math.max(leftHighest[i-1], height[i]);
rightHighest[j] = Math.max(rightHighest[j+1], height[j]);
}
int sum = 0;
for (int i = 1; i < height.length-1; i++){
int area = Math.min(leftHighest[i], rightHighest[i])-height[i];
area = area < 0?0:area;
sum += area;
}
return sum;
}
}
|
No comments:
Post a Comment