接雨水

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。


這是一道困難題,難度確實有點層次.我們先來樸素思想走一波.
要求能接多少雨水,我們可以具化到每個硅谷,每個硅谷能存多少雨水,那么答案就是每個硅谷的雨水所加之和.
對于每一個高度的柱子,我們要求出它的積水量,是等于它左邊高度的最大值與右邊高度的最大值中這兩個值其中的小值減去當前硅谷的高度.
公式為:

怎么理解這句話呢?為什么不是這個硅谷兩旁的高度相比較較小值減去當前硅谷的高度,而是其左右兩邊的最大值呢.

對于這一小塊,我們觀察到積水處的左右兩邊好像跟我們拿其左右兩邊最大值與它身邊兩個的最小值所取到的積水處的值是一樣的.

我們仔細來看看中間那部分.

這一部分如果取兩邊的值,我們將會漏掉上方那一個單位的正方形值,所以對于積水處的兩旁界限我們應該是選取左右兩邊的最大值.

而為什么又要減去積水處的高度呢?我們再來看下面這一部分

其實不用我解釋,現在看這幅圖大家都能理解啦,我們肯定是需要減去它的基礎高度值,才能求得實際上空的空間.也就是硅谷的面積.

所以基于這種求值的思路,我們開始來正式解題.

暴力法解題

我們談到是要取一個硅谷點的左右兩邊最大值來求值.那么每當我們到達一個結點處,遍歷它的左右兩邊找到其左右的最大值就可以完成這一步驟的計算.但由于每一個結點我們都需要遍歷一遍數組,所以時間復雜度為O(2)
我相信大家應該都可以基于暴力能自主完成,這里不做代碼解釋,下面才是算法重點.

動態規劃

我們談到一個節點的左右兩邊的最大值.我們可不可以在計算之前,統計好每一個結點的左右兩邊的最大值.
也就是從左往右開始遍歷,我們可以求得每個結點右邊的最大值.
rightMax[i]=max(rightMax[i+1],height[i])
同理,從右往左遍歷,我們可以求得每個結點左邊的最大值.
leftMax[i]=max(leftMax[i?1],height[i])
總之就是在遍歷計算前,我們打表把所有每個結點的左右兩邊的最大值存儲好,之后我們要求時直接從打表過后的數組里面取就可
代碼為

public int dpMethod(int[] height){int[] leftdp = new int[height.length];int[] rightdp = new int[height.length];int leftMax = 0;int rifhtMax = 0;int res = 0;for(int i = 0;i < height.length;i++){leftdp[i] = leftMax = Math.max(height[i],leftMax);}for(int i = height.length-1;i >= 0;i--){rightdp[i] = rifhtMax = Math.max(height[i],rifhtMax);}for(int i = 0;i < height.length;i++){res += Math.min(leftdp[i],rightdp[i]) - height[i]; }return res;}

時間復雜度為O(n)

單調棧

我們發現硅谷處其實也就是發生破壞一個柱子的單調性時,產生了硅谷.我們可以利用這樣一個特性完成題目的解題.對于每一個結點的索引,我們存放于棧中,每當這個結點的高度小于棧頂元素的值(也就是需要循環遍歷),我們就將其索引值放于棧中.而遇到破壞單調性,也就是一個柱子的高度大于我們的棧頂元素時.我們將棧頂元素彈出,求得此時硅谷處的值.
公式也就是
res += Min(height[peek],height[i])-height[pop]

需要注意的是

我們應該在棧中無元素時,不用再進行求值,因為此時說明是邊界情況,對應此時紅框中的情況,當我們計算完pop處之后,下一次循環,我們將彈出peek處的元素,此時它的左邊沒有元素,也就是對應著此時棧中沒有元素.我們不需要再進行求值.

還有一點不同的是,我們遍歷處的height[j] 與我們的棧頂元素是有一段寬度的,我們計算面積應該帶上寬度的乘積,及寬度長度為 i - peek - 1,對應的情況為

代碼為

public int stack(int[] height){LinkedList<Integer> rain = new LinkedList();int res = 0;for(int i = 0;i < height.length;i++){while(!rain.isEmpty() && height[rain.peek()] < height[i]){int pop = rain.pop();//彈出棧頂元素if(rain.isEmpty()){break;}int left = rain.peek();//獲取棧頂元素的值,還在棧中沒有彈出int h = Math.min(height[i],height[left]) - height[pop];res += h * (i - left - 1);}rain.push(i);}return res;}

時間復雜度為O(n).

雙指針

最后一種解法就是我們的雙指針啦,也是最快的解法.不需要開辟任何空間,只需要常量級別的空間,而且只需要一次遍歷即可完成.

注意到下標 i 處能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值決定。由于數組 leftMax 是從左往右計算，數組 rightMax 是從右往左計算，因此可以使用雙指針和兩個變量代替兩個數組。
遍歷過程中,我們更新左右兩端的最大值.
當左邊的值小于右邊的值時,我們直接拿著左邊的最大值減去當前結點的高度即可.欸?為什么這里我們不需要再次比較左右兩端的最大值,選取其中的較小值呢?
注意啦,我們先判斷左邊的元素是否大于右邊的元素,如果大于我們挪動的是右指針,也就是說明如果右邊的值沒有大于過左邊的值,將一直挪動的是右指針,間接性的把左右兩端的最大值作了比較.
右邊的值小于左邊的值是也是如此.

代碼為所以

public int trap(int[] height) {int left = 0;int right = height.length - 1;int leftMax = 0;int rightMax = 0;int res = 0;while(left < right){leftMax = Math.max(leftMax,height[left]);rightMax = Math.max(rightMax,height[right]);if(height[left] < height[right]){res += leftMax - height[left];left++;}else{res += rightMax - height[right];right--;}}return res;}

時間復雜度為O(n),空間復雜度為O(1)