原題鏈接
題目描述
給出n個數字，表示一個高程圖，高程圖中每一條的寬度為1，
請計算下雨之后這個地形可以存盤多少水
例如
給出[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個單位的雨水（藍色部分）被存盤，
示例
輸入：
[0,1,0,2,1,0,1,3,2,1,2,1]
輸出：
6
參考解法
public class Main {
public static void main(String[] args) {
int a[] = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(trap(a));
}
public static int trap(int[] a) {
// 陣列中最大值的下標
int max_index = 0;
// 最大值左側的極大值
int l = 0;
// 最大值右側的極大值
int r = 0;
int sum = 0;
for (int i = 0; i < a.length; i++) {
max_index = a[i] > a[max_index] ? i : max_index;
}
// System.out.println(max_index);
// 左側的和
for (int i = 0; i < max_index; i++) {
if (a[i] < l)
sum += l - a[i];
else
l = a[i];
}
// 右側的和
for (int i = a.length-1; i > max_index; i--) {
if (a[i] < r)
sum += r - a[i];
else
r = a[i];
}
return sum;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144454.html
標籤：其他