建设网站的建设费用包括,搜索引擎优化时营销关键词,erp管理系统软件有哪些,东莞做网站一年费用终于来到了栈专题#xff0c;想想之前来阿里的时候就是面试了一道栈最终通过了终面#xff0c;也是十分怀念了。
739. Daily Temperatures[Medium]
思路#xff1a;这就是最典型的单调栈问题了。从后向前维护下一个更大值或者下一个更大值的位置。
可以看一下当年面阿里时…终于来到了栈专题想想之前来阿里的时候就是面试了一道栈最终通过了终面也是十分怀念了。
739. Daily Temperatures[Medium]
思路这就是最典型的单调栈问题了。从后向前维护下一个更大值或者下一个更大值的位置。
可以看一下当年面阿里时的博客一切都还记忆犹新
单调栈专题练--下一个更大元素-CSDN博客
至于栈的数据结构先尝试了使用java自身的数据结构Stack但确实慢的让人发指可能其内部各种并行安全机制拖慢了其本身的性能
/*
Author Owen_Q
*/
public class DailyTemperature {public static int[] dailyTemperatures(int[] temperatures) {int len temperatures.length;DequeInteger 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;ListInteger 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;DequeInteger 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 (top0 temperatures[i] temperatures[stack[top]]) {top--;}if (top0) {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 {DequeInteger stack;DequeInteger 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 PairInteger, 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 [) {PairInteger, 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;}
}完美 完结撒花
