在上一篇的學習中，我們學習了棧和隊列的基本知識，以及它們對應都有哪些方法，在什么應用場景下如何使用，并且還對它們進行了模擬實現，而其實對于棧和隊列的相關知識還遠不止于此，而今天我們就對棧與隊列進行復盤，認識更多使用它們的場景，夯實代碼功底吧~

一、常考面試題-思維

以下習題在leetcode都是比較熱門的題，并且大部分都能夠代表一系列的解題方式，推薦大家自己多嘗試幾遍，練熟練透哦~

第一題、最小棧

📚 思路提示：

該題要求我們實現一個擁有"能夠直接獲取棧內最小元素方法"的棧，并且要求時間復雜度為O(1)，要知道我們之前所學習的棧可是沒有這種高能的方法的~而這是為什么呢？

因為當我們把元素壓入棧中之后，想要再對其中的元素進行訪問是做不到的，如果要強行訪問，那么就需要將棧頂元素一個個拿出來，而當找到最小值的那一刻，該棧的元素也就都被掏空了，也就更不用說時間復雜度還達到了O(n)。

當然，做不到是因為只有一個棧，而我們可以采取創建輔助棧的方式，來模擬實現這種"O(1)查找最小元素"的棧，具體的實現步驟如下所述：

📕 創建一個輔助棧，用于存儲當前"最小棧"中的最小值

📕 只有"入棧元素 <= 最小值"時，才入最小棧( == 時必須入棧，否則可能發生"普通棧有兩個最小值，而最小棧只有一個最小值，最小值出棧后，最小棧中就不是當前最小值了"的情況)

📕 需要注意，"最小棧"中的最小值可能被出棧，所以輔助棧存儲的最小值也要跟隨一起改變

📕 注意出棧操作時，保證兩個棧都不為空

? 圖解：

📖 代碼示例：

class MinStack {Stack<Integer> stack1;Stack<Integer> stack2;int n = Integer.MAX_VALUE;public MinStack() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int node) {if (node < n) {n = node;}stack2.push(n);stack1.push(node);}public void pop() {stack1.pop();stack2.pop();if(!stack2.isEmpty() && stack2.peek() >= n){n = stack2.peek();}if(stack2.isEmpty()){n = Integer.MAX_VALUE;}}public int top() {return stack1.peek();}public int getMin() {return stack2.peek();}
}

第二題、字符串解碼

📚 思路提示：

該題要求我們將"數學表達式的字符串"改寫成"展開后的字符串"，光看測試用例大家或許覺得簡單，但看似簡單，其實需要注意的細節還是很多的，比如它還有三個測試用例：

這樣看起來就有些讓人抓心撓肝，難受的不行了。

而對于這題的解決方式，我們仍然是采用"輔助棧"的方法，而且這次我們需要不止一個，而是需要"兩個輔助棧"。

至于需要用兩個輔助棧，是因為我們不能光存"倍數"或者"字符"，因為我們想達到O(n)的時間復雜度，就要求我們遍歷一次成功，但我們可以注意到：

以示例2為參考例子："3 [ a 2 [ c ] ]"? ? ==》 "accaccacc"

想要結果有"cc"，就需要將 [ c ] 于它之前的 2 相對應，而我們遍歷到 [ c ] 的時候，已經越過了 2 ，所以如果我們想不存儲數字，是做不到這一點的。

而如果想有"acc"，我們就必須再將 a 接在 cc 的前邊，但是當我們合成 cc 后，早就遍歷過了 a ，所以我們也必須用一個棧存儲字符，才能得到最終的字符串。

而具體怎么存呢？我們可以通過一個"res"來存儲臨時的字符串，"multi"來存儲臨時的數字，' [ ' 來作為分段的符號，

📕 每當遇到 ' [ ' ，我們便將此時這一組字符串于數字存入棧中，以便不與其他部分搞混

📕 每當遇到 ' ]?' ，我們便將此時的"臨時字符串"與"棧內數字"進行結合

(因為 ' [ ' 前數字是與 ' [?'?后字符串結合后的因子，因此二者匹配)

? 圖解：

📖 代碼示例：

class Solution {public static String decodeString(String s) {int multi = 0;StringBuilder res = new StringBuilder();Stack<String> stack1 = new Stack<>();Stack<Integer> stack2 = new Stack<>();char[] str = s.toCharArray();for(int i = 0;i < str.length;i++){char c = str[i];if(c == '['){stack1.push(res.toString());stack2.push(multi);multi = 0;res = new StringBuilder();}else if(c == ']'){StringBuilder ss = new StringBuilder();int n = stack2.pop();for(int j = 0;j < n;j++){ss.append(res);}res = new StringBuilder(stack1.pop() + ss);}else if(Character.isDigit(c)){multi = multi * 10 + (c - 48);}else {res.append(c);}}return res.toString();}
}

第三題、逆波蘭表達式求值

📚 思路提示：

此題并不難，只要搞清了逆波蘭表達式如何求，并且逆波蘭表達式如何再還原成原式就好了~

所以我們直接看圖，只要了解了過程，這題也就迎刃而解了~

? 圖解：

算數計算式轉逆波蘭表達式：

波蘭表達式求表達式的值：

(用后綴表達式求結果)

📕 遇到數字 放入棧內 遇到運算符 彈出棧頂

📕 兩個元素 第一個元素是右操作數 第二個元素是左操作數

📕 然后再將結果放回棧內

📖 代碼示例：

class Solution {public int evalRPN(String[] tokens) {Stack stack = new Stack();for(int i = 0;i < tokens.length;i++){String s = tokens[i];if(!doNum(s)){stack.push(Integer.valueOf(s));} else {int a = (int)stack.pop();int b = (int)stack.pop();switch(s){case "+":stack.push(b + a); break;case "-":stack.push(b - a); break;case "*":stack.push(b * a); break;case "/":stack.push(b / a); break;}}}return (int)stack.pop();}public boolean doNum(String s){if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){return true;}return false;}
}

二、常考面試題-單調棧

"他向遠方望去，無法看到高山背后的矮山，只能看到一座座更高的山峰。"

(引用靈神的話~)

我們上面已經練習了一部分棧的習題，那么關于這里的單調棧又是什么呢？其實和名字一樣

單調棧：要求從棧的一端，到棧的另一端，元素必須是呈單調遞增或單調遞減的~

而單調棧分為兩種，一種是單調遞增棧，一種是單調遞減棧~

📕 單調遞增棧：從棧低到棧頂，元素單調遞增的棧

📕 單調遞減棧：從棧低到棧頂，元素單調遞減的棧

我們可以舉一個例子來看一下，如何通過一組數據來獲得我們的單調棧：

? 圖解：(該棧為單調遞減棧)

那么單調棧應該運用于哪些場景呢？讓我們做幾道例題試試~

第一題、商品折扣后的最終價格

📚 思路提示：

我們分析一下這道題，我們主要需要做的就是"找出當前價格后的第一個小于它的價格"，并且找到我們需要的較小價格后，就可以將當前價格折扣后的價格計算出來了，也就是說可以將它舍棄掉了(也就是出棧~)

那么可以將價格數組 prices 進行遍歷，使用一個輔助棧來將未被解決的價格(的下標)存入棧中。

然后繼續遍歷與壓棧，直到遇到比目前棧頂價格更小的價格(也就是目標的折扣)，就可以算出目前棧頂價格的折扣價格，并將其出棧操作~

(可能目前的 prices[i] 價格也小于棧頂下一個價格，所以此處應用 "while" 而不是 "if")

最后將棧中剩余未被解決的價格，直接原價出售即可~

怎么樣，很明顯，這也是一道單調棧問題吧~其實單調棧的辨識度還是很高的，只要題中要求你找到一個比一個數值更高/低的元素，并且分析后可以省略之前元素。那么它大概率就是一個單調棧問題~

? 圖解：

📖 代碼示例：

class Solution {public int[] finalPrices(int[] prices) {Deque<Integer> deque = new ArrayDeque<>();int len = prices.length;int[] arr = new int[len];for(int i = 0;i < len;i++){int price = prices[i];while(!deque.isEmpty() && price <= prices[deque.peek()]){int index = deque.pop();arr[index] = prices[index] - prices[i];}deque.push(i);arr[i] = prices[i];}return arr;}
}

第二題、每日溫度

📚 思路提示：

這題的主要思路與上一題還是基本一致的~只不過上一題要找的是越來越小的元素(單調遞增棧)，而我們這題需要找的是越來越大的元素(單調遞減棧)

一樣的思路，遍歷溫度數組，將未被解決的溫度存入棧中(下標)。

如果找到比棧頂溫度更高的溫度，則計算出棧頂溫度與該溫度相差天數，隨后將已得出結果的棧頂溫度出棧，將目前溫度入棧

最后棧中未被解決的溫度，將它們的天數用0代替。

? 圖解：

📖 代碼示例：

class Solution {public int[] dailyTemperatures(int[] temperatures) {int len = temperatures.length;int[] arr = new int[len];Deque<Integer> stack = new ArrayDeque<>();stack.push(0);for(int i = 0;i < len;i++){int num = temperatures[i];while(!stack.isEmpty() && num > temperatures[stack.peek()]){int index = stack.pop();arr[index] = i - index;}stack.push(i);}return arr;}
}

第三題、股票價格跨度

📚 思路提示：

而題中要求我們將傳入的數據，一個個往前進行比較，如果前一天的價格小于今天的價格，那么"入棧的股票價格跨度" += "棧頂元素的股票價格跨度"，并且前一天的前一天也可能小于今天得價格，所以還是while而不是if~(那么這就是一個單調遞減棧)

前兩道題讓我們完成的是一個"方法"，而這道題是想讓我們設計實現一個"類"

前兩道題給我們的是一個數組，我們就對數組進行一個遍歷，然后通過每一步遍歷，同時檢查并刪改棧頂元素即可，而這題我們自己輸入元素，而并非給我們一個數組。

而對于這一點不同，我們的解題方法需要有什么修改呢？讓我們思考一下：

之前我們的棧內只存儲了一個元素(下標)，這是因為我們的數據值在題中所給出的數組中存儲著~而當題目并沒有給我們數組，而是讓我們自己輸入數據時，我們的棧便不能只存儲一個數據了，而是必須將每日的股票價格與跨度同時存儲，所以我們創建的棧應該是<int[]>類型的~

需要注意的是：

📕 由于同時存儲了跨度，當對不滿足單調性的數據進行出棧時，我們僅僅是想在后續訪問過程中忽略該結點的股票價格，而忽略并不代表消失，所以即便后續訪問時跳過它，但它的天數仍是做數的！

📕 所以出棧時，我們需要同時對 "入棧的股票價格跨度" += "棧頂元素的股票價格跨度"，這不僅僅是因為我們要求出該天的跨度，也是為了后續股票訪問到這里時，也一并算上被省略的天數！

? 圖解：

📖 代碼示例：

class StockSpanner {Deque<int[]> stack;public StockSpanner() {stack = new ArrayDeque<int[]>();}public int next(int price) {int day = 1;while(!stack.isEmpty() && stack.peek()[1] <= price){day += stack.pop()[0];}stack.push(new int[] {day,price});return day;}
}

那么這次關于棧與隊列(常考面試題)以及(單調棧)的知識，就為大家分享到這里啦，作者能力有限，如果有講得不清晰或者不正確的地方，還請大家在評論區多多指出，我也會虛心學習的！那我們下次再見哦