棧
當(dāng)前位置的元素不能立刻計(jì)算禾怠,需要隔著一段距離去找另一個(gè)對(duì)應(yīng)的元素。
單調(diào)棧問(wèn)題:
42.接雨水 (hard)
當(dāng)不能繼續(xù)維持單調(diào)遞減棧時(shí)揍诽,就證明能存貯水籽慢,那么把無(wú)法繼續(xù)保持遞減的部分出棧,并算出由出棧部分與當(dāng)前高度的差值所能貯存的水量住诸。關(guān)鍵是確定當(dāng)前位置積水量的方法是驾胆,在當(dāng)前位置兩側(cè)比當(dāng)前位置高的元素。
84.柱狀圖中矩形最大面積 (hard)
如果能維持遞增的關(guān)系贱呐,那么包含當(dāng)前柱子的最大矩形就還不能確定丧诺,因?yàn)槿绻疫吀缶涂梢岳^續(xù)往右側(cè)擴(kuò)展,而如果無(wú)法保持遞增奄薇,那么當(dāng)前柱子小于上個(gè)柱子的高度驳阎。以上個(gè)柱子為高度的矩形面積就可以確定下來(lái)了。此時(shí)出棧無(wú)法保持遞增棧的柱子(即面積已經(jīng)確定的成員)并對(duì)其面積進(jìn)行計(jì)算馁蒂。關(guān)鍵是確定以當(dāng)前柱子為高度的矩形所需要找到當(dāng)前柱子兩側(cè)更矮的柱子呵晚。
739.每日溫度(medium)
從后向前遍歷,因?yàn)樾枰液蠓奖犬?dāng)前位置溫度高的元素沫屡,因此維護(hù)一個(gè)從后向前的遞增棧即可饵隙。
找右邊方向比當(dāng)前大的元素
利用棧代替遞歸:
105.用棧實(shí)現(xiàn)二叉樹(shù)的幾種遍歷(medium)
這里是利用棧去代替遞歸操作
括號(hào)類(lèi)問(wèn)題:
32.最長(zhǎng)有效括號(hào)(hard)
能夠找到匹配對(duì)象則出棧,最后計(jì)算匹配出棧時(shí)的距離谁鳍。
394.字符串解碼(medium)
由于括號(hào)的生長(zhǎng)方式一般是由內(nèi)向外的癞季,在利用棧進(jìn)行操作時(shí)根據(jù)括號(hào)的匹配情況能找到最內(nèi)側(cè)的括號(hào),并根據(jù)匹配的情況依次出棧相應(yīng)成員倘潜。本題目由于會(huì)涉及到括號(hào)外部的multi乘積绷柒,所以需要獨(dú)立為表示次數(shù)的數(shù)字建立棧。數(shù)字先入棧稍后再根據(jù)嵌套情況做處理涮因。
隊(duì)列
102.層序遍歷二叉樹(shù)(medium)
利用隊(duì)列的先進(jìn)先出次序完成對(duì)樹(shù)每層的遍歷
雙端隊(duì)列:
239.滑動(dòng)窗口最大值(hard)
需要從兩側(cè)pop元素废睦,當(dāng)向隊(duì)列中加入新的值時(shí),如果隊(duì)列中有數(shù)值小于當(dāng)前值养泡,那么證明在窗口內(nèi)小于當(dāng)前值的數(shù)字不再起作用就從后方將其pop出來(lái)嗜湃。當(dāng)隊(duì)列中元素的個(gè)數(shù)超過(guò)了窗口的長(zhǎng)度時(shí)則需要從隊(duì)列前端pop掉舊的元素奈应。因此需要用到雙端隊(duì)列來(lái)模擬滑動(dòng)窗口的過(guò)程。
優(yōu)先隊(duì)列:
利用大根堆小根堆進(jìn)行排序
347.前k個(gè)高頻元素(medium)
實(shí)際上是利用優(yōu)先隊(duì)列內(nèi)部實(shí)現(xiàn)是堆的這一特性购披,利用它進(jìn)行一個(gè)快速的排序杖挣。可以指定以結(jié)構(gòu)體中的哪個(gè)元素為參考進(jìn)行排序刚陡,默認(rèn)情況下是利用大根堆進(jìn)行自動(dòng)排序惩妇,若需要小根堆則需要指定priority_queue<<int>,vector<int>,greater<int>> q;
1353.最多可以參加的會(huì)議數(shù)目(medium)
這道題目是典型的貪心算法,先參加當(dāng)前情況下結(jié)束最早的會(huì)議筐乳,此處是利用小根堆排序以較小的時(shí)間復(fù)雜度來(lái)獲得當(dāng)前結(jié)束時(shí)間最早的會(huì)議歌殃。