Java-数据结构-栈与队列(常考面试题与单调栈)
在上一篇的学习中，我们学习了栈和队列的基本知识，以及它们对应都有哪些方法，在什么应用场景下如何使用，并且还对它们进行了模拟实现，而其实对于栈和队列的相关知识还远不止于此，而今天我们就对栈与队列进行复盘，认识更多使用它们的场景，夯实代码功底吧~
一、常考面试题-思维
以下习题在leetcode都是比较热门的题，并且大部分都能够代表一系列的解题方式，推荐大家自己多尝试几遍，练熟练透哦~
第一题、最小栈
📚 思路提示：
该题要求我们实现一个拥有"能够直接获取栈内最小元素方法"的栈，并且要求时间复杂度为O(1)，要知道我们之前所学习的栈可是没有这种高能的方法的~而这是为什么呢？
因为当我们把元素压入栈中之后，想要再对其中的元素进行访问是做不到的，如果要强行访问，那么就需要将栈顶元素一个个拿出来，而当找到最小值的那一刻，该栈的元素也就都被掏空了，也就更不用说时间复杂度还达到了O(n)。
当然，做不到是因为只有一个栈，而我们可以采取创建辅助栈的方式，来模拟实现这种"O(1)查找最小元素"的栈，具体的实现步骤如下所述：
📕 创建一个辅助栈，用于存储当前"最小栈"中的最小值
📕 只有"入栈元素 <= 最小值"时，才入最小栈( == 时必须入栈，否则可能发生"普通栈有两个最小值，而最小栈只有一个最小值，最小值出栈后，最小栈中就不是当前最小值了"的情况)
📕 需要注意，"最小栈"中的最小值可能被出栈，所以辅助栈存储的最小值也要跟随一起改变
📕 注意出栈操作时，保证两个栈都不为空
⭐ 图解：
📖 代码示例：
class MinStack {
Stack<Integer> stack1;
Stack<Integer> stack2;
int n = Integer.MAX_VALUE;
public MinStack() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int node) {
if (node < n) {
n = node;
}
stack2.push(n);
stack1.push(node);
}
public void pop() {
stack1.pop();
stack2.pop();
if(!stack2.isEmpty() && stack2.peek() >= n){
n = stack2.peek();
}
if(stack2.isEmpty()){
n = Integer.MAX_VALUE;
}
}
public int top() {
return stack1.peek();
}
public int getMin() {
return stack2.peek();
}
}第二题、字符串解码
📚 思路提示：
该题要求我们将"数学表达式的字符串"改写成"展开后的字符串"，光看测试用例大家或许觉得简单，但看似简单，其实需要注意的细节还是很多的，比如它还有三个测试用例：
这样看起来就有些让人抓心挠肝，难受的不行了。
而对于这题的解决方式，我们仍然是采用"辅助栈"的方法，而且这次我们需要不止一个，而是需要"两个辅助栈"。
至于需要用两个辅助栈，是因为我们不能光存"倍数"或者"字符"，因为我们想达到O(n)的时间复杂度，就要求我们遍历一次成功，但我们可以注意到：
以示例2为参考例子："3 [ a 2 [ c ] ]" ==》 "accaccacc"
想要结果有"cc"，就需要将 [ c ] 于它之前的 2 相对应，而我们遍历到 [ c ] 的时候，已经越过了 2 ，所以如果我们想不存储数字，是做不到这一点的。
而如果想有"acc"，我们就必须再将 a 接在 cc 的前边，但是当我们合成 cc 后，早就遍历过了 a ，所以我们也必须用一个栈存储字符，才能得到最终的字符串。
而具体怎么存呢？我们可以通过一个"res"来存储临时的字符串，"multi"来存储临时的数字，' [ ' 来作为分段的符号，
📕 每当遇到 ' [ ' ，我们便将此时这一组字符串于数字存入栈中，以便不与其他部分搞混
📕 每当遇到 ' ] ' ，我们便将此时的"临时字符串"与"栈内数字"进行结合
(因为 ' [ ' 前数字是与 ' [ ' 后字符串结合后的因子，因此二者匹配)
⭐ 图解：
📖 代码示例：
class Solution {
public static String decodeString(String s) {
int multi = 0;
StringBuilder res = new StringBuilder();
Stack<String> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
char[] str = s.toCharArray();
for(int i = 0;i < str.length;i++){
char c = str[i];
if(c == '['){
stack1.push(res.toString());
stack2.push(multi);
multi = 0;
res = new StringBuilder();
}else if(c == ']'){
StringBuilder ss = new StringBuilder();
int n = stack2.pop();
for(int j = 0;j < n;j++){
ss.append(res);
}
res = new StringBuilder(stack1.pop() + ss);
}else if(Character.isDigit(c)){
multi = multi * 10 + (c - 48);
}else {
res.append(c);
}
}
return res.toString();
}
}第三题、逆波兰表达式求值
📚 思路提示：
此题并不难，只要搞清了逆波兰表达式如何求，并且逆波兰表达式如何再还原成原式就好了~
所以我们直接看图，只要了解了过程，这题也就迎刃而解了~
⭐ 图解：
算数计算式转逆波兰表达式：
波兰表达式求表达式的值：
(用后缀表达式求结果)
📕 遇到数字 放入栈内 遇到运算符 弹出栈顶
📕 两个元素 第一个元素是右操作数 第二个元素是左操作数
📕 然后再将结果放回栈内
📖 代码示例：
class Solution {
public int evalRPN(String[] tokens) {
Stack stack = new Stack();
for(int i = 0;i < tokens.length;i++){
String s = tokens[i];
if(!doNum(s)){
stack.push(Integer.valueOf(s));
} else {
int a = (int)stack.pop();
int b = (int)stack.pop();
switch(s){
case "+":stack.push(b + a); break;
case "-":stack.push(b - a); break;
case "*":stack.push(b * a); break;
case "/":stack.push(b / a); break;
}
}
}
return (int)stack.pop();
}
public boolean doNum(String s){
if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
return true;
}
return false;
}
}二、常考面试题-单调栈
"他向远方望去，无法看到高山背后的矮山，只能看到一座座更高的山峰。"
(引用灵神的话~)
我们上面已经练习了一部分栈的习题，那么关于这里的单调栈又是什么呢？其实和名字一样
单调栈：要求从栈的一端，到栈的另一端，元素必须是呈单调递增或单调递减的~
而单调栈分为两种，一种是单调递增栈，一种是单调递减栈~
📕 单调递增栈：从栈低到栈顶，元素单调递增的栈
📕 单调递减栈：从栈低到栈顶，元素单调递减的栈
我们可以举一个例子来看一下，如何通过一组数据来获得我们的单调栈：
⭐ 图解：(该栈为单调递减栈)
那么单调栈应该运用于哪些场景呢？让我们做几道例题试试~
第一题、商品折扣后的最终价格
📚 思路提示：
我们分析一下这道题，我们主要需要做的就是"找出当前价格后的第一个小于它的价格"，并且找到我们需要的较小价格后，就可以将当前价格折扣后的价格计算出来了，也就是说可以将它舍弃掉了(也就是出栈~)
那么可以将价格数组 prices 进行遍历，使用一个辅助栈来将未被解决的价格(的下标)存入栈中。
然后继续遍历与压栈，直到遇到比目前栈顶价格更小的价格(也就是目标的折扣)，就可以算出目前栈顶价格的折扣价格，并将其出栈操作~
(可能目前的 prices[i] 价格也小于栈顶下一个价格，所以此处应用 "while" 而不是 "if")
最后将栈中剩余未被解决的价格，直接原价出售即可~
怎么样，很明显，这也是一道单调栈问题吧~其实单调栈的辨识度还是很高的，只要题中要求你找到一个比一个数值更高/低的元素，并且分析后可以省略之前元素。那么它大概率就是一个单调栈问题~
⭐ 图解：
📖 代码示例：
class Solution {
public int[] finalPrices(int[] prices) {
Deque<Integer> deque = new ArrayDeque<>();
int len = prices.length;
int[] arr = new int[len];
for(int i = 0;i < len;i++){
int price = prices[i];
while(!deque.isEmpty() && price <= prices[deque.peek()]){
int index = deque.pop();
arr[index] = prices[index] - prices[i];
}
deque.push(i);
arr[i] = prices[i];
}
return arr;
}
}第二题、每日温度
📚 思路提示：
这题的主要思路与上一题还是基本一致的~只不过上一题要找的是越来越小的元素(单调递增栈)，而我们这题需要找的是越来越大的元素(单调递减栈)
一样的思路，遍历温度数组，将未被解决的温度存入栈中(下标)。
如果找到比栈顶温度更高的温度，则计算出栈顶温度与该温度相差天数，随后将已得出结果的栈顶温度出栈，将目前温度入栈
最后栈中未被解决的温度，将它们的天数用0代替。
⭐ 图解：
📖 代码示例：
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len = temperatures.length;
int[] arr = new int[len];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for(int i = 0;i < len;i++){
int num = temperatures[i];
while(!stack.isEmpty() && num > temperatures[stack.peek()]){
int index = stack.pop();
arr[index] = i - index;
}
stack.push(i);
}
return arr;
}
}第三题、股票价格跨度
📚 思路提示：
而题中要求我们将传入的数据，一个个往前进行比较，如果前一天的价格小于今天的价格，那么"入栈的股票价格跨度" += "栈顶元素的股票价格跨度"，并且前一天的前一天也可能小于今天得价格，所以还是while而不是if~(那么这就是一个单调递减栈)
前两道题让我们完成的是一个"方法"，而这道题是想让我们设计实现一个"类"
前两道题给我们的是一个数组，我们就对数组进行一个遍历，然后通过每一步遍历，同时检查并删改栈顶元素即可，而这题我们自己输入元素，而并非给我们一个数组。
而对于这一点不同，我们的解题方法需要有什么修改呢？让我们思考一下：
之前我们的栈内只存储了一个元素(下标)，这是因为我们的数据值在题中所给出的数组中存储着~而当题目并没有给我们数组，而是让我们自己输入数据时，我们的栈便不能只存储一个数据了，而是必须将每日的股票价格与跨度同时存储，所以我们创建的栈应该是<int[]>类型的~
需要注意的是：
📕 由于同时存储了跨度，当对不满足单调性的数据进行出栈时，我们仅仅是想在后续访问过程中忽略该结点的股票价格，而忽略并不代表消失，所以即便后续访问时跳过它，但它的天数仍是做数的！
📕 所以出栈时，我们需要同时对 "入栈的股票价格跨度" += "栈顶元素的股票价格跨度"，这不仅仅是因为我们要求出该天的跨度，也是为了后续股票访问到这里时，也一并算上被省略的天数！
⭐ 图解：
📖 代码示例：
class StockSpanner {
Deque<int[]> stack;
public StockSpanner() {
stack = new ArrayDeque<int[]>();
}
public int next(int price) {
int day = 1;
while(!stack.isEmpty() && stack.peek()[1] <= price){
day += stack.pop()[0];
}
stack.push(new int[] {day,price});
return day;
}
}那么这次关于栈与队列(常考面试题)以及(单调栈)的知识，就为大家分享到这里啦，作者能力有限，如果有讲得不清晰或者不正确的地方，还请大家在评论区多多指出，我也会虚心学习的！那我们下次再见哦
原文地址：https://blog.csdn.net/ixiaotang_/article/details/145114285
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！