目錄

• 為什么單調棧的時間復雜度是O(n)
• 496. 下一個更大元素 I
• • 方法一：暴力
  • 方法二:單調棧+哈希表
• 739. 每日溫度
• • 單調棧模版解
  • 優化
• 503. 下一個更大元素 II
• • 單調棧+循環遍歷

為什么單調棧的時間復雜度是O(n)

盡管for 循環里面還有while 循環，但是里面的while最多執行n次，所以最大執行2n次，即時間復雜度為O(n)。
不能只看有幾層循環，因為很多情況下內循環是不執行的，可以這樣理解，n個元素每個元素最多進棧一次出棧一次，所以是n

496. 下一個更大元素 I

https://leetcode-cn.com/problems/next-greater-element-i/
給定兩個 沒有重復元素 的數組 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每個元素在 nums2 中的下一個比其大的值。

nums1 中數字 x 的下一個更大元素是指 x 在 nums2 中對應位置的右邊的第一個比 x 大的元素。如果不存在，對應位置輸出 -1 。

示例 1:

輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:
對于num1中的數字4，你無法在第二個數組中找到下一個更大的數字，因此輸出 -1。
對于num1中的數字1，第二個數組中數字1右邊的下一個較大數字是 3。
對于num1中的數字2，第二個數組中沒有下一個更大的數字，因此輸出 -1。

示例 2:

輸入: nums1 = [2,4], nums2 = [1,2,3,4].
輸出: [3,-1]
解釋:
對于 num1 中的數字 2 ，第二個數組中的下一個較大數字是 3 。
對于 num1 中的數字 4 ，第二個數組中沒有下一個更大的數字，因此輸出 -1 。

方法一：暴力

先找到nums1的數在nums2對應的下標，然后從那個下標開始向右遍歷，尋找是否存在。

class Solution {
public:int get_index(vector<int>& nums, int num){for(int i = 0; i < nums.size(); i++){if(num == nums[i]) return i;}return -1;} vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> ans(nums1.size());	//答案數組stack<int> st;for(int i = 0; i < nums1.size(); i++){//首先獲取nums1[i](當前元素)在nums2數組中的下標int start = get_index(nums2,nums1[i]);int flag = 0;for(; start < nums2.size(); start++){if(nums2[start] > nums1[i]){ans[i] = nums2[start];flag = 1;break;   }}if(flag == 0){ans[i] = -1;}flag = 0;}return ans;}
};

方法二:單調棧+哈希表

先忽略nums1，因為nums1中元素在nums2中一定有。
對nums2進行單調棧處理，需要記錄的是一個鍵值對(該元素，該元素右邊第一個比該元素大的元素)。
這個是個典型的單調棧模型：
需要注意：在比較的過程，如果滿足st.back() <= nums2[i]，就說明nums2[i]是大于棧頂元素的第一個元素(因為我們遍歷是向右遍歷的)。
經過這個過程后，留在棧中的元素都符合沒有找到右邊元素大于該元素的條件，所以應該返回-1。

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> ans(nums1.size());	//答案數組vector<int> st;map<int,int> hash_map;for(int i = 0; i < nums2.size(); i++){while(!st.empty() && st.back() < nums2[i]){//說明第一個大于棧頂元素的元素為nums2[i]hash_map[st.back()] = nums2[i];st.pop_back();}st.push_back(nums2[i]);}//如果此時棧中還有元素，說明說明呢？//說明棧中的元素在nums2數組中沒有在右邊找到比它還大的數，所以需要賦值為-1while(!st.empty()){hash_map[st.back()] = -1;st.pop_back();}//將哈希集合中的鍵值對轉換為結果for(int i = 0; i < nums1.size(); i++){ans[i] = hash_map[nums1[i]];}return ans;}
};

739. 每日溫度

https://leetcode-cn.com/problems/daily-temperatures/
請根據每日 氣溫 列表，重新生成一個列表。對應位置的輸出為：要想觀測到更高的氣溫，至少需要等待的天數。如果氣溫在這之后都不會升高，請在該位置用 0 來代替。

例如，給定一個列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的輸出應該是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：氣溫 列表長度的范圍是 [1, 30000]。每個氣溫的值的均為華氏度，都是在 [30, 100] 范圍內的整數。

單調棧模版解

一開始我使用了兩個棧，一個用來存該元素，還有一個用來存該元素的下標，用來計算相差天數，時間復雜度會比較高，也浪費了一些空間。后來發現了只使用一個棧，存下標就行了。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& T) {vector<int> ans(T.size());	//答案數組vector<int> st_index;for(int i = 0; i < T.size(); i++){while(!st_index.empty() && T[st_index.back()] < T[i]){//說明第一個大于棧頂元素的元素為nums2[i]ans[st_index.back()] = (i - st_index.back());st_index.pop_back();}st_index.push_back(i);}//說明棧中的元素在nums2數組中沒有在右邊找到比它還大的數，所以需要賦值為-1while(!st_index.empty()){ans[st_index.back()] = 0;st_index.pop_back();}return ans;}
};

優化

這一題還有KMP的解法，等看到KMP的知識點再做！貼個鏈接
https://leetcode-cn.com/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode-solution/438101

503. 下一個更大元素 II

https://leetcode-cn.com/problems/next-greater-element-ii/
給定一個循環數組（最后一個元素的下一個元素是數組的第一個元素），輸出每個元素的下一個更大元素。數字 x 的下一個更大的元素是按數組遍歷順序，這個數字之后的第一個比它更大的數，這意味著你應該循環地搜索它的下一個更大的數。如果不存在，則輸出 -1。

示例 1:

輸入: [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1 的下一個更大的數是 2；
數字 2 找不到下一個更大的數；
第二個 1 的下一個最大的數需要循環搜索，結果也是 2。

單調棧+循環遍歷

原本next只能在當前元素的右邊，現在有可能出現在左邊了。
我們可以在原數組后面再接一個原數組，這樣就可以完成這樣的效果。
另外需要注意的是：對于壓棧的元素來說，仍然只是需要壓入前n個數，不需要重復將后面鏈接的數組元素壓入。
還需要注意的是：
1、當前元素大于棧頂元素的時候才能進行出棧操作，也就是說，棧中的元素是嚴格單調遞增的，不允許出現等于的情況(這里可能出現重復的元素，所以不能等于)

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();vector<int> ans(n,-1);	//答案數組vector<int> st;for(int i = 0; i < 2 * n; i++){while(!st.empty() && nums[st.back()] < nums[i%n]){ans[st.back()] = nums[i%n];st.pop_back();}if(i < n) st.push_back(i);}return ans;}
};