? leetcode 42
? 給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子奢赂，下雨之后能接多少雨水。
image.png
? 上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下庭惜，可以接 6 個(gè)單位的雨水（藍(lán)色部分表示雨水）
? 目標(biāo)是取凹陷處的面積，第一想法穗酥，既然是凹陷處护赊，那只要記錄每個(gè)位置左邊的最大高度和右邊的最大高度，取這兩者的最小值和本位置的高度比較迷扇，只要本位置的高度低于左右高度之中的最小值百揭，即可計(jì)算凹陷處面積。
? 所以創(chuàng)建兩個(gè)數(shù)組存儲(chǔ)每個(gè)點(diǎn)兩邊的最大高度蜓席。
public int trap(int[] height) {
int sum = 0;
int[] left = new int[height.length];
int[] right = new int[height.length];
for (int i = 1; i < height.length - 1; i++) {
left[i] = Math.max(left[i - 1], height[i - 1]);
}
for (int i = height.length - 2; i >= 0; i--) {
right[i] = Math.max(right[i + 1], height[i + 1]);
}
for (int i = 1; i < height.length - 1; i++) {
int min = Math.min(left[i], right[i]);
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}
? 而實(shí)際上取凹陷處的面積器一，只需要左右高度大于本位置高處即形成凹陷，只需要兩個(gè)額外元素記錄左右最大高度即可厨内，也無需進(jìn)行多次遍歷祈秕，遍歷一遍即可。代碼如下
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int ans = 0;
int leftMax = 0;
int rightMax = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] > leftMax) {
leftMax = height[left];
} else {
ans += leftMax - height[left];
}
left++;
} else {
if (height[right] > rightMax) {
rightMax = height[right];
} else {
ans += rightMax - height[right];
}
right--;
}
}
return ans;
}
? 初始化時(shí)雏胃，記錄最左邊的高度和最右邊的高度為兩邊的最大高度请毛。
? 從左到右遍歷，若本位置的高度大于邊界值瞭亮，則更新對(duì)應(yīng)位置邊界值方仿；若本位置高度小于邊界值，則計(jì)算本位置的面積加入總凹陷面積。
