終于來到了棧專題，想想之前來阿里的時候就是面試了一道棧最終通過了終面，也是十分懷念了。

739. Daily Temperatures[Medium]

思路：這就是最典型的單調棧問題了。從后向前維護下一個更大值或者下一個更大值的位置。

可以看一下當年面阿里時的博客，一切都還記憶猶新

單調棧專題練--下一個更大元素-CSDN博客

至于棧的數據結構，先嘗試了使用java自身的數據結構Stack，但確實慢的讓人發指，可能其內部各種并行安全機制拖慢了其本身的性能

/*
Author Owen_Q
*/
public class DailyTemperature {public static int[] dailyTemperatures(int[] temperatures) {int len = temperatures.length;Deque<Integer> stack = new ArrayDeque<>();int[] result = new int[len];for (int i = len - 1; i >= 0; i--) {while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {stack.pop();}if (!stack.isEmpty()) {result[i] = stack.peek() - i;}stack.push(i);}return result;}
}

多想一下：用鏈表實現棧

再嘗試用鏈表LinkedList來實現棧，速度要快了很多?

/*
Author Owen_Q
*/
public class DailyTemperature {public static int[] dailyTemperaturesWithLinkedList(int[] temperatures) {int len = temperatures.length;List<Integer> stack = new LinkedList<>();int[] result = new int[len];for (int i = len - 1; i >= 0; i--) {while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.get(stack.size() - 1)]) {stack.remove(stack.size() - 1);}if (!stack.isEmpty()) {result[i] = stack.get(stack.size() - 1) - i;}stack.add(i);}return result;}
}

多想一下：用雙端隊列來實現棧

Qwen了一下，ai推薦用ArrayDeque，那么來試試，確實比鏈表還要快一些

/*
Author Owen_Q
*/
public class DailyTemperature {public static int[] dailyTemperaturesWithDeque(int[] temperatures) {int len = temperatures.length;Deque<Integer> stack = new ArrayDeque<>();int[] result = new int[len];for (int i = len - 1; i >= 0; i--) {while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {stack.pop();}if (!stack.isEmpty()) {result[i] = stack.peek() - i;}stack.push(i);}return result;}
}

多想一下：用原始數組手動實現

一切花里胡哨都不如自己手撕，還是手撕大法好呀

/*
Author Owen_Q
*/
public class DailyTemperature {public static int[] dailyTemperaturesManual(int[] temperatures) {int len = temperatures.length;int[] stack = new int[len];int top = -1;int[] result = new int[len];for (int i = len - 1; i >= 0; i--) {while (top>=0 && temperatures[i] >= temperatures[stack[top]]) {top--;}if (top>=0) {result[i] = stack[top] - i;}stack[++top]=i;}return result;}
}

?

155. Min Stack[Medium]

思路：要求設計一個最小棧，不僅要能進行原有棧操作的基礎上，還要能常數復雜度內求出當前棧的最小值。

/*** Author Owen_Q** a stack that supports push, pop, top, and retrieving the minimum element in constant time.* <p>* 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();**/
public interface MinStack {/*** pushes the element val onto the stack.** @param val the element to be pushed*/void push(int val);/*** removes the element on the top of the stack.*/public void pop();/*** gets the top element of the stack.** @return the top element of the stack*/public int top();/*** retrieves the minimum element in the stack.** @return the minimum element in the stack*/public int getMin();
}

其實考慮動態變更的數據結構實時求最小值，首先想到的就是優先隊列或者堆。但這題需要常數復雜度，那么多思考一下。由于棧的特點是先進后出，即棧底元素一定比上方元素存在的時間長。換句話說，如果某個元素在入棧的那一刻沒有成為最小值，那么其將永遠沒有機會再成為最小值了。因為其下方將永遠存在比其小的元素。那么其實我們只需要一個輔助棧，來記錄一下當前棧內最小元素，和原棧元素同步更新。當入棧元素比棧內最小元素小時，則更新棧內最小元素，否則棧內最小元素維持原值。

/*
Author Owen_Q
*/
public class MinStackDeque implements MinStack {Deque<Integer> stack;Deque<Integer> minStack;public MinStackDeque() {stack = new ArrayDeque<>();minStack = new ArrayDeque<>();}@Overridepublic void push(int val) {stack.push(val);if (minStack.isEmpty() || val <= minStack.peek()) {minStack.push(val);} else {minStack.push(minStack.peek());}}@Overridepublic void pop() {if (stack.isEmpty()) {throw new RuntimeException("stack is empty");}stack.pop();minStack.pop();}@Overridepublic int top() {if (stack.isEmpty()) {throw new RuntimeException("stack is empty");}return stack.peek();}@Overridepublic int getMin() {if (minStack.isEmpty()) {throw new RuntimeException("stack is empty");}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();*/

多想一下：用鏈表模擬棧

想著優化一下，但是由于數組的大小未知，因此不能直接手撕，想到可以嘗試手動模擬鏈表來實現棧。恰巧，不難發現，其實上面使用的兩個棧完全是一模一樣的，因此完全可以把棧最小值當成鏈表節點的一部分，說干就干

/*
Author Owen_Q
*/
public class MinStackNodes implements MinStack {private static class StackNode {int val;int minVal;StackNode next;public StackNode(int val, int minVal, StackNode next) {this.val = val;this.minVal = minVal;this.next = next;}}StackNode stack;public MinStackNodes() {stack = null;}@Overridepublic void push(int val) {if (stack == null) {stack = new StackNode(val, val, null);} else {stack = new StackNode(val, Math.min(val, stack.minVal), stack);}}@Overridepublic void pop() {if (stack == null) {throw new RuntimeException("stack is empty");}stack = stack.next;}@Overridepublic int top() {if (stack == null) {throw new RuntimeException("stack is empty");}return stack.val;}@Overridepublic int getMin() {if (stack == null) {throw new RuntimeException("stack is empty");}return stack.minVal;}
}/*** 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();*/

效果拔群

20. Valid Parentheses[Easy]

思路：括號驗證，括號問題其實很容易想到棧，直接用棧模擬一下即可。最后特判一下如果串長是奇數那么直接返回失敗即可

/*
Author Owen_Q
*/
public class ParenthesesValidator {public static boolean isValid(String s) {int len = s.length();char[] stack = new char[len];int top = 0;if ((len & 1) == 1) {return false;}for (int i = 0; i < len; i++) {char c = s.charAt(i);if (c == '(') {stack[top++] = ')';} else if (c == '[') {stack[top++] = ']';} else if (c == '{') {stack[top++] = '}';} else {if (top == 0 || stack[--top] != c) {return false;}}}return top == 0;}
}

394. Decode String[Medium]

思路：一般存在遞歸嵌套的結構都首先想到棧，這里棧需要維護兩個值，一個是前序字母序列，還有一個就是需要重復的次數。然后用一個變量實時維護當前字符串，另一個變量將重復次數從字符串轉換為數字。于是操作就變得很清晰了，如果遇到字母或者數字，就維護兩個特定的變量。每次遇到左括號時，將維護的字符串和重復次數加入棧內，并將兩個變量清空。每次遇到右括號時，則將棧頂元素出棧，獲得前序字母序列和重復次數。于是將當前維護的字符串變量重復特定次數后加上前序字母序列，組成新的字符串再維護到當前變量中。

/*
Author Owen_Q
*/
public class StringDecoder {private static class DecoderNode {int count;StringBuffer str;DecoderNode next;public DecoderNode(int count, StringBuffer str, DecoderNode next) {this.count = count;this.str = str;this.next = next;}}public static String decodeString(String s) {int len = s.length();StringBuffer st = new StringBuffer();int cnt = 0;DecoderNode stack = null;for (int i = 0; i < len; i++) {char c = s.charAt(i);if (c <= '9' && c >= '0') {cnt = cnt * 10 + c - '0';} else if (c == '[') {stack = new DecoderNode(cnt, st, stack);st = new StringBuffer();cnt = 0;} else if (c == ']') {if (stack == null) {throw new RuntimeException("stack is empty");}int stackCount = stack.count;for (int j = 0; j < stackCount; j++) {stack.str.append(st);}st = stack.str;stack = stack.next;} else {st.append(c);}}return st.toString();}
}

用鏈表維護棧是真的好用，效率直接拉滿

多想一下：轉棧為DFS

有句話叫dfs問題都可以轉化為棧問題，那么這題其實就是典型的dfs轉化而來的棧，那么復原用dfs實現一下試試

/*
Author Owen_Q
*/
public class StringDecoder {public static String decodeStringWithDfs(String s) {return dfs(s, 0).getValue().toString();}private static Pair<Integer, StringBuffer> dfs(String s, int pos) {StringBuffer st = new StringBuffer();int cnt = 0;int len = s.length();while (pos < len) {char c = s.charAt(pos);if (c <= '9' && c >= '0') {cnt = cnt * 10 + c - '0';} else if (c == '[') {Pair<Integer, StringBuffer> pair = dfs(s, pos + 1);StringBuffer stackStr = pair.getValue();for (int j = 0; j < cnt; j++) {st.append(stackStr);}cnt = 0;pos = pair.getKey();} else if (c == ']') {return new Pair<>(pos, st);} else {st.append(c);}pos++;}return new Pair<>(cnt, st);}
}

?84. Largest Rectangle in Histogram[Hard]

思路：求直方圖的最大矩形區域，這個和當年阿里面試題簡直有異曲同工之妙。最大01子矩陣問題（單調棧優化）_01最大子矩陣-CSDN博客

在原有單調棧求下一個最小值（最大值的變種）基礎上，要分別求元素的前后方的最小值。

再回憶一下單調棧。針對每個位置，會將棧中所有更大的數全都出站，那么此時棧定元素就是下一個更小的數。接下來要求上一個更小的數。我們再繼續思考出入棧的過程，剛剛說到，此時將當前數入棧，那么當前數再次出棧的時候棧頂元素一定還是下一個更小的數。而恰巧，當前數出棧的時候，就說明了上一個更小的數出現了，因為只有更小的數才能驅使棧內元素出棧。總結而言，當棧內元素出棧時，當前元素是出棧元素的上一個更小元素，出棧后的棧頂元素是出棧元素的下一個更小的元素。

再總結一下，針對單調棧，如果只需要求下一個更小元素，可以在枚舉位置處獲取到。但如果想知道上一個更小元素，則需要等到元素出棧后才能獲取到

/*
Author Owen_Q
*/
public class LargestHistogramRectangle {public static int largestRectangleArea(int[] heights) {int len = heights.length;int[] stack = new int[len];int top = -1;int result = 0;for (int i = len - 1; i >= 0; i--) {while (top >= 0 && heights[i] <= heights[stack[top]]) {int now = heights[stack[top]];top--;int width = top == -1 ? len - i - 1 : stack[top] - i - 1;result = Math.max(result, width * now);}stack[++top] = i;}while (top >= 0) {int now = heights[stack[top]];top--;int width = top == -1 ? len : stack[top];result = Math.max(result, width * now);}return result;}
}

完美

完結撒花

?