刷題31-收集雨水

原題連結

題目描述

給出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;
	}
}