友誼路街道網(wǎng)站建設(shè)google登錄入口
目錄
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ù)。
?