目錄

1. 單調(diào)棧的定義

2.?單調(diào)棧的常見(jiàn)用途

3.?案例分析

3.1?暴力解法

?3.2?單調(diào)棧

?4.?單調(diào)?？偨Y(jié)

---

1. 單調(diào)棧的定義

單調(diào)棧顧名思義，就是棧內(nèi)的元素是單調(diào)的。根據(jù)棧內(nèi)元素的單調(diào)性的不同，可以分為：

單調(diào)遞增棧：棧內(nèi)元素是單調(diào)遞增的棧。

單調(diào)遞減棧：棧內(nèi)元素是單調(diào)遞減的棧。

2.?單調(diào)棧的常見(jiàn)用途

單調(diào)棧的用途：給定一個(gè)序列，指定一個(gè)序列中的元素，求解該元素?左側(cè)/右側(cè)?第一個(gè)比自身? ? 小/大的元素。

這便是單調(diào)棧的常見(jiàn)用途。下面結(jié)合具體的例子來(lái)理解單調(diào)棧哈！N

3.?案例分析

原題鏈接：

496. 下一個(gè)更大元素 I - 力扣（LeetCode）https://leetcode.cn/problems/next-greater-element-i/

題目描述：

nums1?中數(shù)字?x?的 下一個(gè)更大元素 是指?x?在?nums2 中對(duì)應(yīng)位置 右側(cè) 的 第一個(gè) 比?x?大的元素。

給你兩個(gè) 沒(méi)有重復(fù)元素 的數(shù)組?nums1 和?nums2 ，下標(biāo)從 0 開(kāi)始計(jì)數(shù)，nums1?是?nums2?的子集。

對(duì)于每個(gè) 0 <= i < nums1.length ，找出滿足 nums1[i] == nums2[j] 的下標(biāo) j ，并且在 nums2 確定 nums2[j] 的 下一個(gè)更大元素 。如果不存在下一個(gè)更大元素，那么本次查詢的答案是 -1 。

返回一個(gè)長(zhǎng)度為?nums1.length 的數(shù)組 ans 作為答案，滿足 ans[i] 是如上所述的 下一個(gè)更大元素 。

3.1?暴力解法

暴力解法的思路就比較簡(jiǎn)單了。我們先初始化一個(gè)數(shù)組?ret，用他的下標(biāo)表示 nums2?中的每一個(gè)元素，對(duì)應(yīng)下標(biāo)的值表示右側(cè)第一個(gè)比它大的元素。然后從后往前(從前向后也行的)遍歷 nums2?數(shù)組中的元素，遍歷每一個(gè)元素時(shí)向后找比該元素更大的數(shù)，如果找到則將對(duì)應(yīng)的結(jié)果保存到?下標(biāo)為遍歷元素的位置處，如果沒(méi)有找到的話就將 -1?保存到下標(biāo)為遍歷元素的位置處。

得到了 nums2?數(shù)組中每個(gè)元素的右邊第一個(gè)比自身大的元素后，只需要遍歷一次?nums1?數(shù)組，在 ret?數(shù)組中找到結(jié)果就行啦！！

假設(shè)?nums2?數(shù)組的大小為?N，在求 nums2?數(shù)組中的每一個(gè)元素右側(cè)第一個(gè)比自身大的數(shù)時(shí)，時(shí)間復(fù)雜度是一個(gè)等差數(shù)列的求和，即?O(N*N) 。在遍歷?nums1?數(shù)組時(shí)，因?yàn)?nums1?數(shù)組中的元素是nums2?數(shù)組中元素的子集，遍歷 nums1?的時(shí)間復(fù)雜度為?O(N)，所以總的時(shí)間復(fù)雜度為：O(N^2)。

int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{int ret[10010];int j;for(int i = nums2Size - 1; i>=0;i--){for(j =  i + 1; j < nums2Size; j++){if(nums2[j] > nums2[i]){ret[nums2[i]] = nums2[j];break;}}if(j == nums2Size){ret[nums2[i]] = -1;}}*returnSize = nums1Size;int* array = (int*)malloc(sizeof(int)*nums1Size);for(int i = 0;i<nums1Size;i++){array[i] = ret[nums1[i]];}return array;
}

?3.2?單調(diào)棧

單調(diào)棧的應(yīng)用思路和雙指針?biāo)惴ù篌w思路是一致的。先分析暴力解法怎么做，然后分析具體題目，找到其中隱藏的性質(zhì)，從而達(dá)到優(yōu)化時(shí)間效率的目的。

emm怎么分析的就不說(shuō)了，后面會(huì)總結(jié)的。經(jīng)過(guò)分析該問(wèn)題發(fā)現(xiàn)：在向右找比自身大的元素時(shí)，哪些下標(biāo)更大的，但是值卻更小的元素是不可能作為結(jié)果輸出到?ret 數(shù)組的。

?分析到這里我們就可以用單調(diào)棧（為啥呢？找的是右側(cè)第一個(gè)比自身大的元素，第一這兩個(gè)字很能說(shuō)明問(wèn)題）來(lái)解決問(wèn)題了！！我們這里使用的是用數(shù)組模擬的棧哈！效率比STL更高一點(diǎn)。向右找比自身大元素時(shí)，需要從后往前遍歷?nums2?數(shù)組。

我們還是以上面的 3 4 7 2 5?來(lái)舉例分析，開(kāi)始遍歷到 5?這個(gè)元素，此時(shí)棧為空，那就表明 5?這個(gè)元素右側(cè)沒(méi)有比自身大的元素(這里也能夠說(shuō)明為啥向右找需要從后往前遍歷)，將結(jié)果保存到?ret?數(shù)組。然后將 5?壓入棧中。遍歷到 2?時(shí)發(fā)現(xiàn) 2?小于棧頂?shù)脑?5，表明 2?這個(gè)元素右側(cè)第一個(gè)比自身大的元素是 5，將結(jié)果保存到?ret?數(shù)組中。遍歷到 7?時(shí)，發(fā)現(xiàn) 7?大于棧頂?shù)脑?2，這就是我們剛才說(shuō)的，2?是不可能作為結(jié)果輸出的，所以需要將棧頂?shù)?2?彈出。彈出之后棧頂?shù)脑鼐褪?5?啦，同樣?小于 7，但下標(biāo)大于 7?的下標(biāo)，需要再次彈出。此時(shí)我們發(fā)現(xiàn)棧里面已經(jīng)沒(méi)有元素了，說(shuō)明 7?的右側(cè)沒(méi)有比自身大的元素?返回 -1。然后將 7?壓入棧中。其他的元素就同理啦！

?

同樣假設(shè)?nums2?數(shù)組的大小為?N，我們經(jīng)過(guò)分析不難發(fā)現(xiàn)，nums2?中的元素?最多被?壓棧一次，彈棧一次，所以找?nums2?數(shù)組中?右側(cè)第一個(gè)?比自身大的數(shù)的時(shí)間復(fù)雜度為?O(N)，遍歷nums1數(shù)組輸出結(jié)果時(shí)也是?O(N)，因此總的時(shí)間復(fù)雜度就是?O(N)。

int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int stack[nums2Size + 1], top = 0;int ret[10010];for(int i = nums2Size - 1; i >= 0; i--){while(top && nums2[i] >= stack[top]){top--;}if(top){ret[nums2[i]] = stack[top];}else{ret[nums2[i]] = -1;}stack[++top] = nums2[i];}int* array = (int*)malloc(sizeof(int)*nums1Size);for(int i = 0;i<nums1Size;i++){array[i] = ret[nums1[i]];}*returnSize = nums1Size;return array;
}

?4.?單調(diào)?？偨Y(jié)

單調(diào)棧的常見(jiàn)用途就是這個(gè)啦！顯然是有四種情況的：

1：向左找第一個(gè)比自身大的數(shù)。

2：向左找第一個(gè)比自身小的數(shù)。

3：向右找第一個(gè)比自身大的數(shù)。

4：向右找第一個(gè)比自身小的數(shù)。

通過(guò)以上的解題我們可能會(huì)有以下問(wèn)題：

1：從前往后遍歷還是從后往前遍歷？

答：向右找數(shù)從后往前遍歷，向左找數(shù)從前往后遍歷。

2：彈棧的條件之一是大于等于還是小于等于？

答：找比自身大的數(shù)是大于等于正在遍歷的數(shù)，找比自身小的數(shù)是小于等于正在遍歷的數(shù)。

?