?

目錄

方法一：雙指針法

?方法二：動態規劃

方法三：單調棧

---

42. 接雨水 - 力扣（LeetCode）

?

黑色的是柱子，藍色的是雨水，我們先來觀察一下雨水的分布情況:
雨水落在凹槽之間，在一個凹槽的左右都會有兩個柱子，兩個柱子高度可能相同也可能不同，柱子的高低決定了凹槽的雨水的高度，雨水的高度等于兩個柱子較低的高度。

方法一：雙指針法

時間復雜度：O（N^2）;

空間復雜度：O(1)；

缺點：會超時;

思想：統計各個所在位置的左邊最高高度和右邊最高位置（第一個和最后一個柱子所在位置不用統計，他們不可能會接收雨水），然后算出各個位置雨水面積（兩邊的最高高度的較小值 - 當前位置的柱子的面積），最后將各個位置的面積相加得到總面積。

?具體實現：

class Solution {
public:int trap(vector<int>& height) {//面積和int sum = 0;for(int i = 0; i < height.size(); i++){//第一個和最后一個不用統計if(i == 0 || i == height.size() - 1)continue;int maxLeft = height[i];int maxRight = height[i];//統計右邊for(int j = i + 1; j < height.size(); j++){maxRight = max(maxRight,height[j]);}//統計左邊for(int j = i - 1; j >= 0; j--){maxLeft = max(maxLeft,height[j]);}//高度計算int h = min(maxLeft,maxRight) - height[i];if(h > 0)sum += h;}return sum;}
};

?方法二：動態規劃

時間復雜度為 O(N)；

空間復雜度為 O(N);

思路：在方法一的基礎上我們知道，只要知道各個位置的左右最高高度，通過計算就可以求得各個位置的面積，再相加就可以得到總面積。所以就需要遍歷數組來找到左右最高高度，方法一使用雙指針來求左右最高高度，每走到柱子位置就向左右方向進行統計，實際上是進行了重復計算的，導致時間復雜度為O(N^2)。因為柱子的位置都不會變，對于每個柱子，相對的左右最高高度也是不會變的，所以只需要遍歷兩次，把每個位置的左右最高高度計算出來放在兩個數組中，最后再計算面積就行了。

class Solution {
public:int trap(vector<int>& height) {//動態規劃做法//小于等于2個直接返回if(height.size() <= 2)return 0;//左邊最高高度--數組初始化為0vector<int> maxLeft(height.size(),0);//右邊最高高度--數組初始化為0vector<int> maxRight(height.size(),0);//遍歷一次數組記錄各個位置的左邊最高高度maxLeft[0] = height[0];for(int i = 1; i < maxLeft.size(); i++){maxLeft[i] = max(height[i],maxLeft[i - 1]);}//遍歷一次數組記錄各個位置的右邊最高高度maxRight[maxRight.size() - 1] = height[height.size() - 1];for(int i = maxRight.size() - 2; i >= 0; i--){maxRight[i] = max(height[i],maxRight[i + 1]);}//求和int sum = 0;for(int i = 0; i < height.size(); i++){int count = min(maxLeft[i],maxRight[i]) - height[i];if(count > 0){sum += count;}}return sum;}
};

方法三：單調棧

空間復雜度：O(n)；

時間復雜度：O(n)；

使用單調棧使站內元素有序，然而單調棧沒有現成的容器，所以需要我們自己維持元素有序；

那么棧內有序是（棧底->棧頂） 小->大 還是 大->小呢？答案是大->小；當下一個柱子高度小于棧頂元素時就入棧，就能維持棧內有序，當遇到下一個柱子高度大于棧頂元素時就將棧頂pop掉，再將當前的棧頂元素與下一個柱子的高度比較就可以得到較小值，然后就和上面一樣計算面積了。

class Solution {
public:int trap(vector<int>& height) {//如果數組個數兩個及以下，直接returnif(height.size() <= 2)return 0;//創建單調棧（棧頂->棧底==小->大），存放下標值stack<int> st;st.push(0);//統計面積int sum = 0;//行方向計算for(int i = 1; i < height.size(); i++){//1.下一個元素小于棧頂元素if(height[i] < height[st.top()]){st.push(i);}//2.下一個元素等于棧頂元素--pop棧頂元素的下標，push下一個元素的下標else if(height[i] == height[st.top()]){st.pop();st.push(i);}//3.下一個元素大于棧頂元素--形成凹槽接收雨水，計算雨水面積else{while(!st.empty() && height[i] > height[st.top()]){//中間的凹槽下標int mid = st.top();st.pop();if(!st.empty()){//高度計算int h = min(height[st.top()],height[i]) - height[mid];//寬度計算int w = i - st.top() - 1;//面積sum += h * w;}}st.push(i);}}return sum;}
};

?