739. 每日溫度

思路

首先想到的當(dāng)然是暴力解法，兩層for循環(huán)，把至少需要等待的天數(shù)就搜出來了。時間復(fù)雜度是O(n^2)

那么接下來在來看看使用單調(diào)棧的解法。

?什么時候用單調(diào)棧呢？

通常是一維數(shù)組，要尋找任一個元素的右邊或者左邊第一個比自己大或者小的元素的位置，此時我們就要想到可以用單調(diào)棧了。時間復(fù)雜度為O(n)。

例如本題其實就是找找到一個元素右邊第一個比自己大的元素，此時就應(yīng)該想到用單調(diào)棧了。

那么單調(diào)棧的原理是什么呢？為什么時間復(fù)雜度是O(n)就可以找到每一個元素的右邊第一個比它大的元素位置呢？

單調(diào)棧的本質(zhì)是空間換時間，因為在遍歷的過程中需要用一個棧來記錄右邊第一個比當(dāng)前元素高的元素，優(yōu)點是整個數(shù)組只需要遍歷一次。

更直白來說，就是用一個棧來記錄我們遍歷過的元素，因為我們遍歷數(shù)組的時候，我們不知道之前都遍歷了哪些元素，以至于遍歷一個元素找不到是不是之前遍歷過一個更小的，所以我們需要用一個容器（這里用單調(diào)棧）來記錄我們遍歷過的元素。

在使用單調(diào)棧的時候首先要明確如下幾點：

• 單調(diào)棧里存放的元素是什么？

單調(diào)棧里只需要存放元素的下標(biāo) i?就可以了，如果需要使用對應(yīng)的元素，直接T[i]就可以獲取。

• 單調(diào)棧里元素是遞增呢？ 還是遞減呢？

注意以下講解中，順序的描述為 從棧頭到棧底的順序，因為單純的說從左到右或者從前到后，不說棧頭朝哪個方向的話，大家一定比較懵。

這里我們要使用遞增循序（再強調(diào)一下是指從棧頭到棧底的順序），因為只有遞增的時候，棧里要加入一個元素i的時候，才知道棧頂元素在數(shù)組中右面第一個比棧頂元素大的元素是i。

即：如果求一個元素右邊第一個更大元素，單調(diào)棧就是遞增的，如果求一個元素右邊第一個更小元素，單調(diào)棧就是遞減的。

文字描述理解起來有點費勁，接下來我畫了一系列的圖，來講解單調(diào)棧的工作過程，大家再去思考，本題為什么是遞增棧。

使用單調(diào)棧主要有三個判斷條件。

• 當(dāng)前遍歷的元素T[i]小于棧頂元素T[st.top()]的情況
• 當(dāng)前遍歷的元素T[i]等于棧頂元素T[st.top()]的情況
• 當(dāng)前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況

把這三種情況分析清楚了，也就理解透徹了。

接下來我們用temperatures = [73, 74, 75, 71, 71, 72, 76, 73]為例來逐步分析，輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]。

---

首先先將第一個遍歷元素加入單調(diào)棧

---

加入T[1] = 74，因為T[1] > T[0]（當(dāng)前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況）。

我們要保持一個遞增單調(diào)棧（從棧頭到棧底），所以將T[0]彈出，T[1]加入，此時result數(shù)組可以記錄了，result[0] = 1，即T[0]右面第一個比T[0]大的元素是T[1]。

---

加入T[2]，同理，T[1]彈出

---

加入T[3]，T[3] < T[2] （當(dāng)前遍歷的元素T[i]小于棧頂元素T[st.top()]的情況），加T[3]加入單調(diào)棧。

---

加入T[4]，T[4] == T[3] （當(dāng)前遍歷的元素T[i]等于棧頂元素T[st.top()]的情況），此時依然要加入棧，不用計算距離，因為我們要求的是右面第一個大于本元素的位置，而不是大于等于！

---

加入T[5]，T[5] > T[4] （當(dāng)前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況），將T[4]彈出，同時計算距離，更新result?

---

T[4]彈出之后， T[5] > T[3] （當(dāng)前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況），將T[3]繼續(xù)彈出，同時計算距離，更新result?

---

直到發(fā)現(xiàn)T[5]小于T[st.top()]，終止彈出，將T[5]加入單調(diào)棧

---

加入T[6]，同理，需要將棧里的T[5]，T[2]彈出

---

同理，繼續(xù)彈出

---

此時棧里只剩下了T[6]

---

加入T[7]， T[7] < T[6] 直接入棧，這就是最后的情況，result數(shù)組也更新完了。

此時可能就疑惑了，那result[6] , result[7]怎么沒更新啊，元素也一直在棧里。

其實定義result數(shù)組的時候，就應(yīng)該直接初始化為0，如果result沒有更新，說明這個元素右面沒有更大的了，也就是為0。

以上在圖解的時候，已經(jīng)把，這三種情況都做了詳細的分析。

• 情況一：當(dāng)前遍歷的元素T[i]小于棧頂元素T[st.top()]的情況
• 情況二：當(dāng)前遍歷的元素T[i]等于棧頂元素T[st.top()]的情況
• 情況三：當(dāng)前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況

通過以上過程，大家可以自己再模擬一遍，就會發(fā)現(xiàn)：只有單調(diào)棧遞增（從棧口到棧底順序），就是求右邊第一個比自己大的，單調(diào)棧遞減的話，就是求右邊第一個比自己小的。

代碼如下：

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] answer = new int[temperatures.length];//小的話一直壓棧記錄，大的話就下表相減求距離/**如果當(dāng)前遍歷的元素 大于棧頂元素，表示 棧頂元素的 右邊的最大的元素就是 當(dāng)前遍歷的元素，所以彈出 棧頂元素，并記錄如果棧不空的話，還要考慮新的棧頂與當(dāng)前元素的大小關(guān)系否則的話，可以直接入棧。注意，單調(diào)棧里 加入的元素是 下標(biāo)。*/Stack<Integer> st = new Stack<>();st.push(0);for (int i = 1; i < temperatures.length; i++) {if (temperatures[i] > temperatures[st.peek()]){//如果當(dāng)前元素大于棧頂元素//遍歷棧，如果碰到當(dāng)前元素小于等于棧頂元素時，將當(dāng)前元素的下標(biāo)放入棧中//如果當(dāng)前元素大于棧頂元素，棧頂元素為下標(biāo)的值為 i- st.popwhile (!st.isEmpty() && temperatures[i] > temperatures[st.peek()]){if (temperatures[i] > temperatures[st.peek()]){int stIndex = st.pop();answer[stIndex] = i - stIndex;}}st.push(i);}else {//當(dāng)前元素小于等于棧頂元素st.push(i);}}return answer;}
}

---

496.下一個更大元素 I

思路

這題秒了基本沒看卡哥的題解，但思路基本也是與卡哥的一致。但需要注意的細節(jié)點是，每次 i 遍歷完之后需要對棧stack 進行清空處理，防止本次遺留元素影響到下一次層的循環(huán)中。

并且我將結(jié)果數(shù)組 res[] 均初始化為了-1，具體思路見代碼：

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {//nums1 是 nums2 的子集int[] res = new int[nums1.length];Arrays.fill(res,-1);Stack<Integer> st = new Stack<>();//找出num1[i] == num2[j]的j 值for (int i = 0; i < nums1.length; i++) {for (int j = 0; j < nums2.length; j++) {if (nums1[i] == nums2[j]){//確定 nums2[j] 的 下一個更大元素st.push(j);}if (!st.isEmpty() && nums2[j] > nums2[st.peek()]){res[i] = nums2[j];st.pop();}}st.clear();}return res;}
}

---