題目描述
給定n?個非負(fù)整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子绝页，下雨之后能接多少雨水荠商。
上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下续誉，可以接 6 個單位的雨水（藍(lán)色部分表示雨水）莱没。感謝 Marcos?貢獻(xiàn)此圖。
示例:
輸入:[0,1,0,2,1,0,1,3,2,1,2,1]輸出:6
分析
題目容易被所給的圖帶偏酷鸦，其實給出簡單的xy坐標(biāo)圖饰躲，就很容易想到解法朴译。
關(guān)鍵是理解能存水的是單向遞增（遞減）的節(jié)點，存水的數(shù)量是任意兩個遞增（遞減）節(jié)點間的數(shù)值小的節(jié)點所決定属铁，公式為：（小節(jié)點值-區(qū)間內(nèi)節(jié)點值）眠寿。
思路是從左往右，找遞增節(jié)點焦蘑，算出可存水?dāng)?shù)量盯拱，再從右往左找遞增，但這時已經(jīng)知道最大值節(jié)點（從左往右時得到）例嘱，所以不用遍歷整個數(shù)組狡逢，到最大值就可以結(jié)束。
代碼
class Solution {
? ? public int trap(int[] height) {
? ? ? ? if(height.length == 0)
? ? ? ? ? ? return 0;
? ? ? ? int water = 0;
? ? ? ? int maxIndex = 0;
? ? ? ? int max = height[maxIndex];
? ? ? ? for (int i = 1; i < height.length; i++) {
? ? ? ? ? ? int cur = height[i];
? ? ? ? ? ? if (cur >= max) {
? ? ? ? ? ? ? ? if (maxIndex > -1) {
? ? ? ? ? ? ? ? ? ? for (int j = maxIndex + 1; j < i; j++) {
? ? ? ? ? ? ? ? ? ? ? ? water += max - height[j];
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? maxIndex = i;
? ? ? ? ? ? ? ? max = cur;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int end = maxIndex;
? ? ? ? maxIndex = height.length - 1;
? ? ? ? max = height[maxIndex];
? ? ? ? for (int i = height.length - 2; i >= end; i--) {
? ? ? ? ? ? int cur = height[i];
? ? ? ? ? ? if (cur >= max) {
? ? ? ? ? ? ? ? if (maxIndex > -1) {
? ? ? ? ? ? ? ? ? ? for (int j = maxIndex - 1; j > i; j--) {
? ? ? ? ? ? ? ? ? ? ? ? water += max - height[j];
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? maxIndex = i;
? ? ? ? ? ? ? ? max = cur;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return water;
? ? }
}
