终于来到了栈专题，想想之前来阿里的时候就是面试了一道栈最终通过了终面，也是十分怀念了。
739. Daily Temperatures[Medium]
思路：这就是最典型的单调栈问题了。从后向前维护下一个更大值或者下一个更大值的位置。
可以看一下当年面阿里时的博客，一切都还记忆犹新
至于栈的数据结构，先尝试了使用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<>();
}
@Override
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
} else {
minStack.push(minStack.peek());
}
}
@Override
public void pop() {
if (stack.isEmpty()) {
throw new RuntimeException("stack is empty");
}
stack.pop();
minStack.pop();
}
@Override
public int top() {
if (stack.isEmpty()) {
throw new RuntimeException("stack is empty");
}
return stack.peek();
}
@Override
public 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;
}
@Override
public void push(int val) {
if (stack == null) {
stack = new StackNode(val, val, null);
} else {
stack = new StackNode(val, Math.min(val, stack.minVal), stack);
}
}
@Override
public void pop() {
if (stack == null) {
throw new RuntimeException("stack is empty");
}
stack = stack.next;
}
@Override
public int top() {
if (stack == null) {
throw new RuntimeException("stack is empty");
}
return stack.val;
}
@Override
public 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;
}
}
完美
完结撒花
