---

前言

---

提示：如果讓我送給年輕人四個(gè)字，就是：量力而行。 量力而行不會(huì)失眠，不會(huì)啃老，不會(huì)為各種考試焦慮。順其自然活得輕松。其實(shí)，量力而行最易大展宏圖。

棧在常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)中也是比較常用的，一些經(jīng)典的題目對(duì)于理解棧很有幫助，就那他們練手吧

1. 括號(hào)匹配問(wèn)題

棧的典型題目，棧常用在括號(hào)匹配，表達(dá)式計(jì)算等等，我看就來(lái)看看這個(gè)最經(jīng)典的問(wèn)題：

參考題目介紹：20. 有效的括號(hào) - 力扣（LeetCode）


對(duì)于這個(gè)題目來(lái)說(shuō)，還是比較簡(jiǎn)單的，要處理的問(wèn)題難題時(shí)判斷符號(hào)是否一組，我們可以先用Hash將所有的符合存儲(chǔ)下來(lái)，左半邊就做key，右半邊做value。遍歷字符串的時(shí)候，遇到左半邊符號(hào)就入棧，遇到右半邊的符號(hào)就與棧頂?shù)姆?hào)進(jìn)行比較，不匹配就返回false；

public static boolean isValid(String s) {if (s.length() < 2) {return false;}HashMap<Character, Character> map = new HashMap<Character, Character>();map.put('[', ']');map.put('(', ')');map.put('{', '}');Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (map.containsKey(c)) {stack.push(c);} else {if (!stack.isEmpty()) {// 拿到棧頂?shù)淖罄ㄌ?hào)Character left = stack.pop();Character right = map.get(left);if (right != c) {return false;}} else {return false;}}}return stack.isEmpty();}

當(dāng)然類(lèi)似的題目還有很多，有難有易，可以多殺殺，挫挫銳氣哈哈哈🤣，這里我就不一一舉例🌰了

2. 最小棧問(wèn)題

參考題目介紹：155. 最小棧 - 力扣（LeetCode）


不知到你會(huì)不會(huì)和我一樣題目還沒(méi)理解什么意思的，別慌，那我們就來(lái)看看，這個(gè)題要怎么解。我覺(jué)得本題的關(guān)鍵在于getMin()到底表示什么，我們可以畫(huà)一個(gè)圖；

我們看到這個(gè)圖，大致已經(jīng)有了思路，Min棧內(nèi)，中間-2元素，對(duì)它的理解就是解題的關(guān)鍵。

題目要求在常數(shù)時(shí)間內(nèi)獲取到棧中的最小值，也就是我們不能在getMin()的時(shí)候去計(jì)算，而是直接返回值，也就說(shuō)只能在push和pop中做一些操作了。

棧的特性時(shí)先進(jìn)后出，這個(gè)很重要，我們可以這么做，我們將元素（a）存入棧中的時(shí)候，就把當(dāng)前的最小值（m）記錄下來(lái)，也就是說(shuō)如果a時(shí)棧頂，最小是就是m，我們可以直接返回。

這樣的話(huà)我們就可以設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，使得每個(gè)元素a與其相應(yīng)的最小值m時(shí)刻保持一致，所以我們需要一個(gè)輔助棧，與元素棧插入和刪除保持一致，用來(lái)存儲(chǔ)每個(gè)元素對(duì)應(yīng)的最小值。

• 當(dāng)元素要入棧的時(shí)候，我們?nèi)‘?dāng)前輔助棧的棧頂元素與之比較，該元素小，就將這個(gè)值存入輔助棧中；
• 當(dāng)一個(gè)元素要出棧時(shí)，我們把輔助棧的棧頂元素一并出棧

這樣的話(huà)，在任意時(shí)刻，棧內(nèi)元素的最小值就存儲(chǔ)在輔助棧的棧頂元素中。

這樣的話(huà)代碼寫(xiě)起來(lái)就非常簡(jiǎn)單了🤣

class MinStack {private static Stack<Integer> xStack;private static Stack<Integer> minStack;public MinStack() {xStack = new Stack<>();minStack = new Stack<>();// 占位符minStack.push(Integer.MAX_VALUE);}public void push(int val) {xStack.push(val);minStack.push(Math.min(val,minStack.peek()));}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

有最小棧那會(huì)不會(huì)有最大棧呢？哈哈哈，他來(lái)了

3. 最大棧

參考題目介紹：716. 最大棧 - 力扣（LeetCode）

設(shè)計(jì)一個(gè)最大棧數(shù)據(jù)結(jié)構(gòu)，及支持棧操作，有支持查找棧中最大元素。

這個(gè)題和上一題相反，處理方法上一致，一個(gè)普通的?？梢灾С智叭N操作，push(x),pop()和top()，這里我們需要考慮的是后面的操作peekMax()和popMax()。

對(duì)于peekMax()，我們可以用另一個(gè)棧來(lái)存儲(chǔ)每個(gè)位置對(duì)應(yīng)的最大值，比如第一個(gè)棧的元素為[2,1,5,3,9]，那么第二個(gè)棧的元素就是[2,2,5,5,9]。在push(x)操作時(shí)，只需要將第二個(gè)棧頂元素和x的最大值入棧就行，而pop()操作只需要將第二個(gè)棧進(jìn)行出棧。

對(duì)于popMax()，由于我們指導(dǎo)當(dāng)前棧中最大元素值，我們就可以將兩個(gè)棧同時(shí)出棧，并存儲(chǔ)第一個(gè)棧出棧的所有值。當(dāng)某個(gè)時(shí)刻第一個(gè)棧中的出棧元素等于當(dāng)前棧中的最大值時(shí)，我們就找到了最大元素。此時(shí)我們將之前的第一個(gè)棧的所有元素重新入棧，并同步更新到第二棧中，就完成了popMax()操作；

代碼展示如下：

import java.util.Stack;class MaxStack {public static Stack<Integer> xStack;public static Stack<Integer> maxStack;public MaxStack() {xStack = new Stack<Integer>();maxStack = new Stack<Integer>();}public void push(int val) {xStack.push(val);int max = maxStack.isEmpty() ? val : maxStack.peek();maxStack.push(max > val ? max : val);}public int pop() {maxStack.pop();return  xStack.pop();}public int top() {return xStack.peek();}public int peekMax() {return maxStack.peek();}public int popMax() {int max = peekMax();Stack<Integer> stack = new Stack<Integer>();while(top() != max){stack.push(pop());}pop();while(!stack.isEmpty()){push(stack.pop());}return max;}}

---

總結(jié)

提示：棧的操作有時(shí)需要一個(gè)輔助棧，來(lái)幫助解決問(wèn)題。