深入淺出了解單調(diào)棧和單調(diào)隊(duì)列
袁廚攜袁記菜館全體工作人員祝大家在新的一年，健健康康，開開心心。發(fā)量暴增，錢包超大。
哎，元旦假期結(jié)束了，又要繼續(xù)搬磚了，我們接著做題吧，今天我們好好說說單調(diào)棧和單調(diào)隊(duì)列。其實(shí)很容易理解，單調(diào)棧就是棧內(nèi)單調(diào)遞增或單調(diào)遞減的棧，棧內(nèi)元素是有序的，單調(diào)隊(duì)列同樣也是。
下面我們通過幾個(gè)題目由淺入深，一點(diǎn)一點(diǎn)挖透他們吧！
提綱
單調(diào)隊(duì)列
劍指 Offer 59 - II. 隊(duì)列的最大值
題目描述：
請(qǐng)定義一個(gè)隊(duì)列并實(shí)現(xiàn)函數(shù) max_value 得到隊(duì)列里的最大值
若隊(duì)列為空，pop_front 和 max_value 需要返回 -1
示例 1：
輸入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
輸出: [null,null,null,2,1,2]
示例 2：
輸入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
輸出: [null,-1,-1]
題目解析：
我們先來拆解下上面的示例 1
其實(shí)我覺得這個(gè)題目的重點(diǎn)在理解題意上面，可能剛開始刷題的同學(xué)，對(duì)題意理解不夠透徹，做起來沒有那么得心應(yīng)手，通過上面的圖片我們簡(jiǎn)單了解了一下題意，那我們應(yīng)該怎么做才能實(shí)現(xiàn)上述要求呢？
下面我們來說一下雙端隊(duì)列。我們之前說過的隊(duì)列，遵守先進(jìn)先出的規(guī)則，雙端隊(duì)列則可以從隊(duì)頭出隊(duì)，也可以從隊(duì)尾出隊(duì)，不用遵守先進(jìn)先出的規(guī)則，我們先通過一個(gè)視頻來簡(jiǎn)單了解下雙端隊(duì)列。
我們可以用雙端隊(duì)列做輔助隊(duì)列，用輔助隊(duì)列來保存當(dāng)前隊(duì)列的最大值。我們同時(shí)定義一個(gè)普通隊(duì)列和一個(gè)雙端單調(diào)隊(duì)列。普通隊(duì)列就正常執(zhí)行入隊(duì)，出隊(duì)操作。max_value 操作則返回咱們的雙端隊(duì)列的隊(duì)頭即可。下面我們來看一下代碼的具體執(zhí)行過程吧。
我們來對(duì)視頻進(jìn)行解析
1.我們需要維護(hù)一個(gè)單調(diào)雙端隊(duì)列，上面的隊(duì)列則執(zhí)行正常操作，下面的隊(duì)列隊(duì)頭元素則為上面隊(duì)列的最大值
2.出隊(duì)時(shí)，我們需要進(jìn)行對(duì)比兩個(gè)隊(duì)列的隊(duì)頭元素是否相等，如果相等則同時(shí)出隊(duì)，則出隊(duì)后的雙端隊(duì)列的頭部仍為上面隊(duì)列中的最大值。
3.入隊(duì)時(shí)，我們需要維持一個(gè)單調(diào)遞減的雙端隊(duì)列，因?yàn)槲覀冃枰_保隊(duì)頭元素為最大值嘛。
題目代碼：
239.滑動(dòng)窗口最大值
題目描述：
給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。
返回滑動(dòng)窗口中的最大值。
示例1：
輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3 輸出：[3,3,5,5,6,7]
題目解析：
題目讓我們找出每個(gè)滑動(dòng)窗口的最大值，那么題目具體含義是怎樣呢？
就是為了讓我們輸出每個(gè)窗口的最大值，那我們思考一下，我們一個(gè)數(shù)組一共有多少窗口呢？
比如我們這個(gè)例子中，我們的窗口長(zhǎng)度為 3 ，數(shù)組長(zhǎng)度為 8，我們的窗口每次移動(dòng)一位，所以我們一共有 8 - （3 - 1）也就是 8 - 3 + 1。所以我們返回?cái)?shù)組的長(zhǎng)度是跟原數(shù)組長(zhǎng)度和滑動(dòng)窗口的長(zhǎng)度有關(guān)的。
也就是 winlen = len（數(shù)組長(zhǎng)度） - k（滑動(dòng)窗口長(zhǎng)度） + 1。下面我們來看一個(gè)視頻，相信通過這個(gè)視頻，大家一下就能搞懂啦。
下面我們對(duì)視頻進(jìn)行拆解。
1.先將我們第一個(gè)窗口的所有值按照規(guī)則存入單調(diào)雙端隊(duì)列中，單調(diào)隊(duì)列里面的值為單調(diào)遞減的。如果發(fā)現(xiàn)隊(duì)尾元素小于要加入的元素，則將隊(duì)尾元素出隊(duì)，直到隊(duì)尾元素大于等于新元素時(shí)，再讓新元素入隊(duì)，目的就是維護(hù)一個(gè)單調(diào)遞減的隊(duì)列。第一個(gè)窗口的所有值入隊(duì)之后情況，如下圖。是因?yàn)?3 要入隊(duì)時(shí)，此時(shí)隊(duì)中有 1 ，不能保證單調(diào)遞減，所以需要 1 出隊(duì)，然后 3 入隊(duì)， -1 入隊(duì)時(shí)，隊(duì)中有 3 ，滿足單調(diào)，所以 -1 可以入隊(duì)。
2.我們將第一個(gè)窗口的所有值，按照單調(diào)隊(duì)列的規(guī)則入隊(duì)之后，因?yàn)殛?duì)列為單調(diào)遞減，所以隊(duì)頭元素必為當(dāng)前窗口的最大值，則將隊(duì)頭元素添加到數(shù)組中。
3.移動(dòng)窗口，判斷當(dāng)前窗口前的元素是否和雙端隊(duì)列隊(duì)頭元素相等，如果相等則出隊(duì)，此時(shí)滑動(dòng)窗口的最大值發(fā)生改變了。
4.繼續(xù)然后按照規(guī)則進(jìn)行入隊(duì)，維護(hù)單調(diào)遞減隊(duì)列，這里和第一條規(guī)則一致。
5.每次將隊(duì)頭元素存到返回?cái)?shù)組里。
6.返回?cái)?shù)組
是不是一下就搞懂啦。你真帥，下面我們來看一下代碼吧。
題目代碼
單調(diào)棧
leetcode 155 最小棧
設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
push(x) —— 將元素 x 推入棧中。
pop() —— 刪除棧頂?shù)脑亍?/p>
top() —— 獲取棧頂元素。
getMin() —— 檢索棧中的最小元素。
輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
輸出：
[null,null,null,null,-3,null,0,-2]
題目解析
感覺這個(gè)題目的難度就在讀懂題意上面，讀懂之后就沒有什么難的了，我們?cè)谏厦娴幕瑒?dòng)窗口的最大值已經(jīng)進(jìn)行了詳細(xì)描述，其實(shí)這個(gè)題目和那個(gè)題目思路一致。
該題讓我們?cè)O(shè)計(jì)一個(gè)棧，該棧具有的功能有，push，pop，top等操作，并且能夠返回棧的最小值。比如此時(shí)棧中的元素為 5，1，2，3。我們執(zhí)行 getMin() ，則能夠返回 1。這塊是這個(gè)題目的精髓所在，見下圖， 這個(gè)題目也可以不利用輔助棧解決，但是不符合本文主題，所以在這里先不進(jìn)行詳細(xì)描述。大致思路為，把當(dāng)前最小值用一個(gè)變量保存，需要入棧的值小于當(dāng)前最小值時(shí)，先把當(dāng)前最小值入棧，再將需要入棧的值入棧，并更新當(dāng)前最小值。如果大于當(dāng)前最小值，則直接入棧。getMin()函數(shù)則直接返回變量保存的值即可。下面我們來看一下我們借助輔助棧，如何解決這個(gè)題目吧。
我們一起先通過一個(gè)視頻先看一下具體解題思路，通過視頻一定可以整懂的，我們注意觀察棧 B 內(nèi)的元素。
我們來對(duì)視頻進(jìn)行解析
1.我們執(zhí)行入棧操作時(shí)，先觀察需要入棧的元素是否小于棧 B 的棧頂元素，如果小于則兩個(gè)棧都執(zhí)行入棧操作。
2.棧 B 的棧頂元素則是棧 A 此時(shí)的最小值。則 getMin() 只需返回棧 B 的棧頂元素即可。
3.出棧時(shí)，需要進(jìn)行對(duì)比，若棧 A 和棧 B 棧頂元素相同，則同時(shí)出棧，出棧后B 的棧頂保存的仍為此時(shí)棧 A 的最小元素
題目代碼
leetcode 739 每日溫度
題目描述：
請(qǐng)根據(jù)每日 氣溫 列表，重新生成一個(gè)列表。對(duì)應(yīng)位置的輸出為：要想觀測(cè)到更高的氣溫，至少需要等待的天數(shù)。如果氣溫在這之后都不會(huì)升高，請(qǐng)?jiān)谠撐恢糜?0 來代替。
示例1：
輸入：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
輸出：arr = [1, 1, 4, 2, 1, 1, 0, 0]
示例2：
輸入：temperatures = [30,30,31,45,31,34,56]
輸出：arr = [2,1,1,3,1,1,0]
題目解析
其實(shí)我們可以換種方式理解這個(gè)題目，比如我們 temperatures[0] = 30,則我們需要找到后面第一個(gè)比 30 大的數(shù)，也就是 31，31的下標(biāo)為 2，30 的下標(biāo)為 0 ，則我們的返回?cái)?shù)組 arr[0] = 2。理解了題目之后我們來說一下解題思路。
遍歷數(shù)組，數(shù)組中的值為待入棧元素，待入棧元素入棧時(shí)會(huì)先跟棧頂元素進(jìn)行對(duì)比，如果小于等于該值則入棧，如果大于則將棧頂元素出棧，新的元素入棧。
例如棧頂為69，新的元素為72，則69出棧，72入棧。并賦值給 arr，69 的索引為4，72的索引為5，則 arr[4] = 5 - 4 = 1，這個(gè)題目用到的是單調(diào)棧的思想，下面我們來看一下視頻解析。
注：棧中的括號(hào)內(nèi)的值，代表索引對(duì)應(yīng)的元素，我們的入棧的為索引值，為了便于理解將其對(duì)應(yīng)的值寫在了括號(hào)中
leetcode 42 接雨水
這道接雨水也是一道特別經(jīng)典的題目，一道必刷題目，我們也用單調(diào)棧來解決。下面我們來看一下題目吧
題目描述：
給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。
示例1：
輸入：height =[0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
示例2：
輸入：height =[4,2,0,3,2,5]
輸出：9
示例2：
輸入：[4,3,2,0,1,1,5
輸出：13
題目解析：
看了上面的示例剛開始刷題的同學(xué)可能有些懵逼，那我們結(jié)合圖片來理解一下，我們就用示例3的例子進(jìn)行舉例，他的雨水到底代表的是什么。輸入代表的是黃色箱子的個(gè)數(shù)，藍(lán)色箱子代表雨水?dāng)?shù)量?？p隙之間可以裝多少水
說明：上面是由數(shù)組 [4,3,2,0,1,1,5]表示的高度圖，在這種情況下，可以接 13個(gè)單位的雨水（見下圖）。
上圖則為我們的題目描述，是不是理解了呢？你也可以這樣理解我們?cè)诘厣戏胖昧巳舾筛叨鹊狞S色箱子，他們中間有空隙，然后我們想在他們里面插入若干藍(lán)色箱子，并保證插入之后，這些箱子的左視圖和右視圖都不能看到藍(lán)色箱子。 好啦題目我們已經(jīng)理解了，下面我們來看一下接雨水問題到底該怎么做，其實(shí)原理也很簡(jiǎn)單，我們通過我們的例3來進(jìn)行說明。 首先我們依次入棧4，3，2，0我們的數(shù)組前四個(gè)元素是符合單調(diào)棧規(guī)則的。但是我們的第五個(gè)1，是大于0的。那我們就需要0出棧1入棧。但是我們這樣做是為了什么呢？有什么意義呢？別急我們來看下圖。
上圖我們的，4，3，2，0已經(jīng)入棧了，我們的另一個(gè)元素為1，棧頂元素為0，棧頂下的元素為2。那么我們?cè)谶@一層接到的雨水?dāng)?shù)量怎么算呢？2，0，1這三個(gè)元素可以接住的水為一個(gè)單位(見下圖)這是我們第一層接到水的數(shù)量。 注：能接到水的情況，肯定是中間低兩邊高的情況
因?yàn)槲覀冃枰S護(hù)一個(gè)單調(diào)棧，所以我們則需要將0出棧1入棧，那么此時(shí)棧內(nèi)元素為4，3，2，1。下一位元素為1，我們?nèi)霔?，此時(shí)棧內(nèi)元素為4，3，2，1，1。 下一元素為5，棧頂元素為1，棧頂?shù)南乱辉厝詾?，則需要再下一個(gè)元素，為2，那我們求當(dāng)前層接到的水的數(shù)量。 注：棧內(nèi)保存的應(yīng)是索引值，這里為了便于理解用了value值
我們是通過2，1，1，5這四個(gè)元素求得第二層的接水?dāng)?shù)為1*3=3;1是因?yàn)閙in(2-1,5-1)=min(1,4)得來的，大家可以思考一下木桶效應(yīng)。裝水的多少，肯定是按最短的那個(gè)木板來的，所以高度為1，3的話是因?yàn)?的索引為6，2的索引為2，他們之間共有三個(gè)元素（3，4，5）也就是3個(gè)單位。所以為6-2-1=3。 將1出棧之后，我們棧頂元素就變成了2，下一元素變成了3，那么3，2，5這三個(gè)元素同樣也可以接到水。
這是第三層的接水情況，能夠接到4個(gè)單位的水，下面我們繼續(xù)出棧2，那么我們的4，3，5仍然可以接到水啊。
這是我們第四層接水的情況，一共能夠接到5個(gè)單位的水，那么我們總的接水?dāng)?shù)加起來，那就是1+3+4+5=13。你學(xué)會(huì)了嗎？別急還有動(dòng)圖我們，我們?cè)賮砩钊肜斫庖还?
題目代碼：
好啦，咱們的單調(diào)隊(duì)列和單調(diào)棧的題目到這里就算總結(jié)完畢啦，希望對(duì)你能有一點(diǎn)點(diǎn)幫助。
原文標(biāo)題：深入淺出搞通單調(diào)隊(duì)列單調(diào)棧
文章出處：【微信公眾號(hào)：嵌入式ARM】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。
責(zé)任編輯：haq
原文標(biāo)題：深入淺出搞通單調(diào)隊(duì)列單調(diào)棧
文章出處：【微信號(hào)：gh_c472c2199c88，微信公眾號(hào)：嵌入式微處理器】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
淺聊深入淺出RISC-V調(diào)試
嵌入式環(huán)形隊(duì)列與消息隊(duì)列的實(shí)現(xiàn)原理
深入淺出系列之代碼可讀性
深入淺出談TDR阻抗測(cè)試
深入淺出帶你搞懂-MOSFET柵極電阻
【大語言模型：原理與工程實(shí)踐】探索《大語言模型原理與工程實(shí)踐》
深入淺出帶你了解磁共振成像（MRI）基本原理
怎么理解負(fù)頻率呢？射頻人眼中的負(fù)頻率
TC3xx的HSM中有沒有單調(diào)計(jì)數(shù)器？
深入淺出理解三極管
深入淺出了解高邊驅(qū)動(dòng)在汽車應(yīng)用中的挑戰(zhàn)
【年度精選】2023年度top5榜單——電機(jī)控制資料
深入淺出理解PagedAttention CUDA實(shí)現(xiàn)
labview 隊(duì)列最前端插入的應(yīng)用
簡(jiǎn)析控制系統(tǒng)的穩(wěn)定性判據(jù)
工商網(wǎng)監(jiān)
評(píng)論