目錄

一，每日溫度

二，下一個更大的元素I

三，下一個更大的元素II

四，接雨水

小結：

---

?單調棧是一種特殊的棧結構，里面的元素按照單調遞增或者遞減的順序排列。常用于解決元素左邊或者右邊比它大或者小的問題。

一，每日溫度

題目鏈接：739. 每日溫度 - 力扣（LeetCode）

【題目描述】

?對于給定的一個temperatures數組，每個元素表示當天的溫度。對于每天的溫度，求出下一次更高的溫度出現在幾天后。

【算法】單調棧

我們可以維護一個棧結構，先將數組的首元素入棧，然后開始遍歷這個數組，如果遍歷到的數組元素比棧頂元素小，那么就入棧；如果相等，也入棧；當遍歷到的數組元素比此時棧頂的元素大時，記錄此時相隔的天數，然后將棧頂元素彈出，繼續比較棧頂的元素和數組元素的大小，直到棧頂元素小于或者等于棧頂元素，此時將該數組元素入棧。然后接著遍歷下一個數組元素，依次循環。

由于題目中求的是相隔的天數，所以我們不需要將數組元素入棧，只需入棧該元素的下標即可，這樣就可以直接計算相隔的天數：數組元素對應的下標減去棧頂元素對應的下標，就是該棧頂元素與下一個更高溫度相隔的天數。?

圖示：（以題目中的示例1為例）

可以發現，棧中的元素（下標對應的元素）始終保持單調遞減（從棧底到棧頂），因此成為單調棧。?

【代碼】

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n=temperatures.size();vector<int> ans(n,0);stack<int> st;//存儲下標st.push(0);for(int i=1;i<n;i++){//遇到溫度大于棧頂的，就一直出棧，保持遞減性while(!st.empty()&&temperatures[st.top()]<temperatures[i]){int index=st.top();st.pop();ans[index]=i-index;}st.push(i);}return ans;}
};

時間復雜度O(N)，每個元素最多入棧依次。空間復雜度O(N)?

二，下一個更大的元素I

題目鏈接：496. 下一個更大元素 I - 力扣（LeetCode）

【題目描述】

本題存在兩個數組，nums1是nums2的子集，對于nums1數組的每個元素，求出這些元素在對應nums2數組中的下一個更大的元素。如果不存在，則為-1

【算法】單調棧

本題與上一題的思路一樣，只不過加了一點要求。

求當前元素的下一個更大的元素，就需要維護一個單調棧（單調遞減）。

本題還是求數組nums2上每個元素的下一個更大的元素是多少。所以還是在nums2數組上使用單調棧。和上題的過程一樣，只不過在判斷的時候，還需加上一個條件。

假設找到了當前棧頂的下一個更大元素k，還需判斷棧頂元素是否在nums1中出現過，如果該元素在nums1中出現過，那么就將k記錄在最終結果數組ans中，不過還需要保證和nums1數組的位置一一對應。

所以可以做下預處理工作，將數組nums1中的元素和下標使用哈希表保存起來。

初始化ans數組時，可以全部初始化為-1.

【代碼】

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int n=nums1.size();vector<int> ans(n,-1);unordered_map<int,int> hash;for(int i=0;i<n;i++)hash[nums1[i]]=i;stack<int> st;//單調遞減st.push(0);for(int i=1;i<nums2.size();i++){while(!st.empty()&&nums2[st.top()]<nums2[i]){//判斷是否在nums1中出現過if(hash.count(nums2[st.top()])>0){//求出該元素在nums1中對應的下標int index=hash[nums2[st.top()]];//記錄結果ans[index]=nums2[i];}st.pop();}st.push(i);}return ans;}
};

三，下一個更大的元素II

題目鏈接：503. 下一個更大元素 II - 力扣（LeetCode）

【題目描述】

?求一個數組nums每一個元素的下一個更大的數，該數組是循環數組，數組最后一個元素接下來的元素就是數組的第一個元素。

【算法】單調棧

求下一個更大的元素，單調棧（單調遞減棧）。

大致的方向還是使用單調棧。本題的重點是：如何處理循環數組。

方法一：是將原數組nums在后面再拼接一份。然后使用單調棧求下一個更大的元素。

將兩個nums數組拼接起來，使用單調棧求出每一個元素的下一個更大值，存儲在ans數組中，然后將ans數組的大小減為一半。

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {//拼接兩個數組vector<int> nums1(nums.begin(),nums.end());nums.insert(nums.begin(),nums1.begin(),nums1.end());vector<int> ans(nums.size(),-1);stack<int> st;//單調遞減st.push(0);for(int i=1;i<nums.size();i++){while(!st.empty()&&nums[st.top()]<nums[i]){ans[st.top()]=nums[i];st.pop();}st.push(i);}//將數組減為原來的一般ans.resize(nums.size()/2);return ans;}
};

方法二：也可以不用擴充數組，在遍歷的時候模擬走兩邊nums即可。

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n=nums.size();vector<int> ans(n,-1);stack<int> st;//單調遞減st.push(0);//模擬走兩邊nums//當遍歷完最后一個元素，執行++后,再取模n，會回到數組的開始for(int i=1;i<2*n;i++){while(!st.empty()&&nums[st.top()]<nums[i%n]){ans[st.top()]=nums[i%n];st.pop();}st.push(i%n);}return ans;}
};

四，接雨水

題目鏈接：42. 接雨水 - 力扣（LeetCode）

【解法一】雙指針?

求這些柱子中一共有多少雨水。看每個柱子可以"接"多少雨水。

也就是統計每個柱子上有多少水，然后將每個柱子上的水加起來即可。

問題是如何求每個柱子上有多少水？

對于第i個柱子，求第i個柱子上有多少水，需要求出第i個柱子左邊柱子最高的高度，以及第i個柱子右邊柱子最高的高度，取兩者的最小值，然后再減去當前柱子的高度。

【代碼】

class Solution {
public:int trap(vector<int>& height) {//雙指針int n=height.size();vector<int> maxLeft(n,0);auto maxRight=maxLeft;//記錄左邊最大值maxLeft[0]=height[0];for(int i=1;i<n;i++)maxLeft[i]=max(maxLeft[i-1],height[i]);//記錄右邊最大值maxRight[n-1]=height[n-1];for(int i=n-2;i>=0;i--)maxRight[i]=max(maxRight[i+1],height[i]);int ans=0;for(int i=0;i<n;i++){int count=min(maxLeft[i],maxRight[i])-height[i];if(count>0) ans+=count;}return ans;}
};

【解法二】單調隊列

這種思路是求柱子與柱子之間的雨水量。

首先需要明白，當后一個柱子高度大于前一個柱子高度，那么一定是會有雨水的。

所以我們需要求下一個更大的元素，使用單調遞減棧。

思路，與前面題的思路一致。

---

當遍歷到的元素大于棧頂元素時:

此時的棧頂就是下圖的中間柱子，下標記為mid，對應的高度為height[mid]，將棧頂元素彈出。

此時的棧頂元素st.top()，就是最左邊的柱子，對應的高度為height[st.top()]。

此時遍歷到的元素是最右邊的柱子，下標為i，柱子高度為height[i]。

最后只需計算出中間雨水的長和寬然后相乘即可。

h=min(height[st.top()],height[i])-height[mid]

w=i-st.top()-1

【代碼】

class Solution {
public:int trap(vector<int>& height) {int n=height.size();int ans=0;stack<int> st;//單調遞減st.push(0);for(int i=1;i<n;i++){while(!st.empty()&&height[st.top()]<height[i]){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;ans+=h*w;}}st.push(i);}return ans;}
};

小結：

單調棧常用于解決元素左側或者右側第一個更大后者更小的問題。

核心原理：

• 單調遞增棧：棧內元素從棧底到棧頂遞增，用于尋找更小的元素。

• 單調遞減棧：棧內元素從棧底到棧頂遞減，用于尋找更大的元素。

• 遍歷數組時，若當前元素破壞單調性，則彈出棧頂元素，直到滿足單調性。