终于来到了栈专题，想想之前来阿里的时候就是面试了一道栈最终通过了终面，也是十分怀念了。

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;}
}

完美

完结撒花