当前位置：首页 > news >正文

Java-数据结构-栈与队列(常考面试题与单调栈)

news 来源：原创 2025/5/12 5:51:27

在上一篇的学习中，我们学习了栈和队列的基本知识，以及它们对应都有哪些方法，在什么应用场景下如何使用，并且还对它们进行了模拟实现，而其实对于栈和队列的相关知识还远不止于此，而今天我们就对栈与队列进行复盘，认识更多使用它们的场景，夯实代码功底吧~

一、常考面试题-思维

以下习题在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;}
}

那么这次关于栈与队列(常考面试题)以及(单调栈)的知识，就为大家分享到这里啦，作者能力有限，如果有讲得不清晰或者不正确的地方，还请大家在评论区多多指出，我也会虚心学习的！那我们下次再见哦

一、常考面试题-思维

第一题、最小栈

第二题、字符串解码

第三题、逆波兰表达式求值

二、常考面试题-单调栈

第一题、商品折扣后的最终价格

第二题、每日温度

第三题、股票价格跨度

相关文章：