目錄

• • 題目
  • 思路
  • 暴力法
  • 動態規劃
  • 雙指針法
  • 單調棧

題目

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

輸入：height = [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 個單位的雨水（藍色部分表示雨水）。

示例 2：

輸入：height = [4,2,0,3,2,5]
輸出：9

提示：
n == height.length
0 <= n <= 3 * 10^4
0 <= height[i] <= 10^5

思路

對于數組中的每個元素，最高水位為：兩邊最大高度的較小值 - 當前高度的值
用偽代碼描述：
water[i] = min(left,right) - height[i];
（有一說一，沒想到是對每個元素進行計算的，以為是找到幾個較高點，然后劃分區間分別計算。）
這樣問題就可以化簡為尋找每個元素右邊最大的值和左邊最大的值了。
沒想到這個，我感覺很難往下做下去。

暴力法

使用暴力法，對于遍歷數組的時候，對應的元素找左右最大值,順著上面的思路來一遍：
顯然時間復雜度是O(n^2)的

class Solution { public:int trap(vector<int>& height){int ans = 0;int n = height.size();for(int i = 0; i < n; i++){//找左右最大值int left_max = 0, right_max = 0;for(int j = i; j >= 0; j--)left_max = max(left_max,height[j]);for(int j = i; j < n; j++)right_max = max(right_max,height[j]);//累積此位置的雨水ans += min(left_max,right_max) - height[i];}return ans;} };

動態規劃

之前，對于每個元素的左右最大值我們是在遍歷該元素的時候找的。可以預先找到，存儲下來，計算雨水的時候直接查詢即可。
需要預先構造出兩個數組，用來存放。
填充極大值數組的時候要記住：
從左向右遍歷，每次更新左極大值,當前元素的左極大值只和當前元素和左邊一個元素的左極大值有關。
即：left_max[i] = max(height[i],left_max[i - 1]);
從右向左遍歷，每次更新右極大值,當前元素的右極大值只和當前元素和右邊一個元素的右極大值有關
即:right_max[i] = max(height[i],right_max[i + 1]);
這個方法有兩個細節：
1、考慮輸入數組為空
2、初始化左右極大值數組的第一個元素以及遍歷的起點

顯然，時間復雜度是O(n)的。是遍歷了3次原數組。

class Solution { public:int trap(vector<int>& height){if(height.empty()) return 0;int ans = 0;int n = height.size();vector<int> left_max(n);vector<int> right_max(n);//初始化//第一個元素的左邊沒有元素，所以左極大值就是本身left_max[0] = height[0];//最后一個元素的右邊沒有元素，所以右極大值就是本身right_max[n - 1] = height[n - 1];//從左向右遍歷，每次更新左極大值,當前元素的左極大值只和當前元素和左邊一個元素的左極大值有關for(int i = 1; i < n; i++)left_max[i] = max(height[i],left_max[i - 1]);//從右向左遍歷，每次更新右極大值,當前元素的右極大值只和當前元素和右邊一個元素的右極大值有關for(int i = n - 2; i >= 0; i--)right_max[i] = max(height[i],right_max[i + 1]);for(int i = 0; i < n; i++){ans += min(left_max[i],right_max[i]) -height[i];}return ans;} };

雙指針法

動態規劃是遍歷了兩次，使用雙指針可以實現只遍歷一次就實現填充左右極大值數組。
感覺有個解釋解釋的非常好：
https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/327718

1、明確變量意義

left_max：左邊的最大值，它是從左往右遍歷找到的
right_max：右邊的最大值，它是從右往左遍歷找到的
left：從左往右處理的當前下標
right：從右往左處理的當前下標

2、明確已知定理：

定理一：在某個位置i處，它能存的水，取決于它左右兩邊的最大值中較小的一個。
定理二：當我們從左往右處理到left下標時，左邊的最大值left_max對它而言是可信的，但right_max對它而言是不可信的。（見下圖，由于中間狀況未知，對于left下標而言，right_max未必就是它右邊最大的值）
定理三：當我們從右往左處理到right下標時，右邊的最大值right_max對它而言是可信的，但left_max對它而言是不可信的。

3、得到具體細節

對于位置left而言，它左邊最大值一定是left_max，右邊最大值“大于等于”right_max，這時候，如果left_max<right_max成立，那么它就知道自己能存多少水了。無論右邊將來會不會出現更大的right_max，都不影響這個結果。 所以當left_max<right_max時，我們就希望去處理left下標，反之，我們希望去處理right下標。

4、知道了這些，就可以寫代碼了：

class Solution { public:int trap(vector<int>& height){if(height.empty()) return 0;int ans = 0;int n = height.size();int left = 0,right = n - 1;int left_max = height[left], right_max = height[right];while(left <= right){if(left_max < right_max){//還要判斷left_max與當前的值誰大，如果當前值大，就不需要累積了。if(left_max < height[left]) left_max = height[left];else ans += (left_max - height[left]);left++;}else{//還要判斷left_max與當前的值誰大，如果當前值大，就不需要累積了。if(right_max < height[right]) right_max = height[right];else ans += (right_max - height[right]);right--;}}return ans;} };

單調棧

盡管之前寫過接近8題的單調棧的題目，這一題我使用單調棧的思路感覺并不是很清晰。而且粗略看了官方題解也沒理解具體細節。
下面兩個單調棧的講法都比較好：
我下面使用的圖也是從這兩個地方嫖的。
https://leetcode-cn.com/problems/trapping-rain-water/solution/42-jie-yu-shui-shuang-zhi-zhen-dong-tai-gui-hua-da/
https://leetcode-cn.com/problems/trapping-rain-water/solution/dan-diao-zhan-jie-jue-jie-yu-shui-wen-ti-by-sweeti/
單調棧計算雨水的方式是按照行計算的：


還有兩個個需要注意的地方：
1、我們構建的是單調遞減棧，一旦發現添加的柱子高度大于棧頭元素了，此時就出現凹槽了，棧頭元素就是凹槽底部的柱子，棧頭第二個元素就是凹槽左邊的柱子，而添加的元素就是凹槽右邊的柱子。
如下圖所示：

2、遇到相同高度的柱子怎么辦。
遇到相同的元素，更新棧內下標，就是將棧里元素（舊下標）彈出，將新元素（新下標）加入棧中。
因為我們要求寬度的時候 如果遇到相同高度的柱子，需要使用最右邊的柱子來計算寬度。

接下來就可以套用模板寫代碼了
這里借鑒了代碼隨想錄的冗余代碼，能夠較好地理解for循環中三個情況具體處理。

class Solution { public:int trap(vector<int>& height){if(height.empty()) return 0;int ans = 0;int n =height.size();vector<int> st;for(int i = 0; i < n; i++){//如果棧為空，或者棧頂元素大于height[i]入棧if( st.empty() || height[i] < height[st.back()]){st.emplace_back(i);}//如果棧不為空且棧頂元素==height[i]，更新棧頂元素，取更右邊的else if(!st.empty() && height[i] == height[st.back()]){st.pop_back();st.emplace_back(i);}//如果棧不為空，且棧頂元素小于height[i]else{while(!st.empty() && height[i] > height[st.back()]){int mid = st.back();st.pop_back();if(!st.empty()){int H = min(height[st.back()],height[i]) - height[mid];int W = i - st.back() -1; //i與st.back()之間的寬度ans += H * W;}}st.emplace_back(i);}}return ans;} };

總結

以上是生活随笔為你收集整理的leetcode 42. 接雨水 思考分析(暴力、动态规划、双指针、单调栈)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。