【Java实习面试算法冲刺】栈、队列与单调栈

第5类题型：栈、队列与单调栈

为什么这一类题你总感觉概念都懂，做题时却分不清该上哪个结构
很多同学看到栈、队列、单调栈这类题时，第一反应都是“概念我知道”。问题在于，真正到了面试现场，难点从来不是背定义，而是你能不能把题意瞬间映射到正确的数据结构。
这类题最容易暴露出几种问题：

• 你知道栈是后进先出，但遇到括号匹配还是没第一时间反应过来。
• 你会写Deque，但push/pop和offer/poll一紧张就容易混。
• 你记住了单调栈“递减 / 递增”的表述，却没理解为什么很多题栈里要存下标。

如果你现在处在“模板知道一点，但题面一拐弯就发虚”的阶段，这一类题非常值得单独梳理。读完这篇，你至少要把 3 件事练熟：先判断该用栈、队列还是单调栈；理解单调栈里为什么经常保存下标；能在面试里解释“当前元素到底在帮谁结算答案”。

1. 核心知识点

这一类题其实是三个模型：

• 栈：后进先出，常见于括号匹配、路径回退。
• 队列：先进先出，常见于层序遍历、广度优先。
• 单调栈：维护“还没找到答案的元素”，常见于“下一个更大元素”。

Java 刷题里，推荐统一使用ArrayDeque：

Deque<Integer>stack=newArrayDeque<>();stack.push(x);stack.pop();stack.peek();Deque<Integer>queue=newArrayDeque<>();queue.offer(x);queue.poll();queue.peek();

Stack类是老 API，实战里一般不优先用。

单调栈的核心理解是：栈里存的往往不是值本身，而是下标，因为你最终要更新的是某个位置的答案。

动画辅助理解：当前元素在帮谁结算答案

这一类题最适合用739. 每日温度建立单调栈直觉。你可以先打开本地动画页：

单调栈：每日温度分步动画

这个动画最值得盯住的是 4 步：

• 栈里保存的是“还没找到更高温度的下标”。
• 当前温度一旦比栈顶对应温度更高，就说明栈顶那一天终于能结算答案了。
• 弹出栈顶后，答案就是当前位置和那个下标的距离。
• 当前下标入栈，继续等待未来更高温度来结算它。

拿temperatures = [73, 74, 75, 71]举例，前两步状态变化可以这样看：

2. 这类题在面试里考什么

这类题常用来区分“知道数据结构定义”和“会把结构用到题里”。

面试官会看：

• 你能不能根据题意快速判断该用栈还是队列。
• 你是否知道单调栈为什么保存的是还没找到答案的下标。
• 你会不会在 Java 里正确使用ArrayDeque。

真正拉开差距的，不是你能不能背出 FIFO / LIFO，而是你能不能解释：为什么这个题里当前元素会和栈顶发生关系，为什么另一些题又要用队列来保证处理顺序。

3. 高频题清单

4. 这类题最容易犯的 3 个错误

1. 明明是括号匹配，却没有第一时间想到栈。
2. 用 JavaStack写题，接口和性能习惯都不够好。
3. 单调栈只记住“维护递减 / 递增”，没理解为什么存下标。

5. 代表题精讲 1

题目

20. 有效的括号

思路

看到括号匹配，第一反应就该是栈。因为右括号需要和“最近一个还没匹配的左括号”对应，这正是后进先出的结构。

做法：

1. 遍历字符串。
2. 遇到左括号就入栈。
3. 遇到右括号，先看栈是否为空；为空直接失败。
4. 弹出栈顶，看是否与当前右括号匹配。
5. 遍历结束后，栈必须为空。

Java 代码

importjava.util.ArrayDeque;importjava.util.Deque;classSolution{publicbooleanisValid(Strings){Deque<Character>stack=newArrayDeque<>();for(charc:s.toCharArray()){if(c=='('||c=='['||c=='{'){stack.push(c);}else{if(stack.isEmpty()){returnfalse;}chartop=stack.pop();if((c==')'&&top!='(')||(c==']'&&top!='[')||(c=='}'&&top!='{')){returnfalse;}}}returnstack.isEmpty();}}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

边界提醒

这题最容易漏掉的边界有两个：一是字符串一开始就是右括号，比如")"；二是遍历结束后栈里还有左括号，比如"(()"。这两个边界正好对应代码里的两个关键判断：stack.isEmpty()和最后的stack.isEmpty()返回值。

如果这是面试现场，你可以这样说

这题是典型的栈题。因为每个右括号都要和最近一个未匹配的左括号对应，所以适合用后进先出的结构。遍历时左括号入栈，右括号就和栈顶匹配。最后如果栈为空，说明所有括号都恰好配对。

6. 代表题精讲 2

题目

739. 每日温度

思路

这题问的是：对于每一天，后面第一个更高温度要等几天。只要出现“右侧第一个更大 / 更小元素”，就应该优先联想到单调栈。

做法：

1. 维护一个单调递减栈，栈里存下标。
2. 遍历当前温度temperatures[i]。
3. 如果当前温度比栈顶下标对应的温度更高，说明栈顶那一天终于找到了答案。
4. 弹出栈顶，答案就是i - poppedIndex。
5. 最后把当前下标入栈。

Java 代码

importjava.util.ArrayDeque;importjava.util.Deque;classSolution{publicint[]dailyTemperatures(int[]temperatures){int[]answer=newint[temperatures.length];Deque<Integer>stack=newArrayDeque<>();for(inti=0;i<temperatures.length;i++){while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){intprevIndex=stack.pop();answer[prevIndex]=i-prevIndex;}stack.push(i);}returnanswer;}}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

边界提醒

这题里栈必须保存下标，而不是温度值本身。因为最终要填的是“还要等几天”，本质是位置差。如果你只存温度值，即使知道74比73大，也没法直接算出应该填多少天。

同时，最后还留在栈里的那些下标不用再特殊处理，它们在答案数组里天然保持0，表示后面再也没有更高温度。

如果这是面试现场，你可以这样说

这题我会归类为单调栈，因为它本质是在找每个位置右侧第一个更大的元素。栈里保存的是还没找到答案的下标，并且对应温度保持单调递减。一旦当前温度比栈顶更高，就说明栈顶那一天的答案找到了，可以直接更新天数差。

7. 其余题模板与关键片段

232. 用栈实现队列

两个栈：一个负责入，一个负责出。

if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}

这里的关键不是“两个栈”这四个字，而是你要理解：只有当outStack空了，才需要把inStack倒过去。这样才能既保持队列顺序，又避免每次操作都重复搬运。

155. 最小栈

可以用辅助栈同步维护最小值：

minStack.push(minStack.isEmpty()?val:Math.min(val,minStack.peek()));

这题的本质不是把最小值现算出来，而是让“当前栈顶对应的最小值”跟随每次入栈、出栈一起同步变化。

8. 这三类结构怎么快速区分

你可以用一个简单判断法：

• 最近匹配、撤销上一步、反向回退，优先想栈。
• 按进入顺序处理、层层扩散、先来先服务，优先想队列。
• 右侧第一个更大 / 更小元素、当前位置帮前面某些位置结算答案，优先想单调栈。

真正写代码前，最好先用一句话说清：

• 我现在维护的是匹配顺序。
• 我现在维护的是处理顺序。
• 我现在维护的是一批还没找到答案的下标。

9. 错题本记录方式

这一类题建议记录：

• 我是如何判断出需要栈 / 队列 / 单调栈的。
• 单调栈里保存的是值还是下标，为什么。
• 当前元素出现时，栈顶元素代表什么状态。
• Java 中push/pop/offer/poll是否写混了。

10. 面试前 3 分钟速记

• 括号匹配，优先想栈。
• 层序遍历、BFS，优先想队列。
• 右侧第一个更大 / 更小元素，优先想单调栈。
• 单调栈通常存下标，不直接存值。
• Java 刷题推荐ArrayDeque。

11. 最后总结：不要只背结构定义，要知道当前元素在做什么

如果你只能记住一句话，那就是：栈、队列、单调栈这类题真正的关键，不是定义本身，而是“当前元素出现时，它和之前元素之间发生了什么关系”。

面试时你只要能按这个顺序去讲，思路就会稳定很多：

1. 这题要维护的是匹配顺序、处理顺序，还是等待结算的状态。
2. 当前元素出现时，是入栈 / 入队等待，还是负责结算之前的元素。
3. 我维护的是值、字符，还是下标。
4. 最终答案是靠匹配成功、顺序处理完成，还是位置差更新出来的。

这样你不只是会做一道题，而是真的开始掌握这一类数据结构题的共性。

上期速递：【Java实习面试算法冲刺】链表

感谢阅读，记得点赞、关注、收藏，欢迎各位评论区交流！！！