java算法母题30道-第3篇-栈与队列
·
算法母题30道（第3篇）：栈与队列（11-15）
系列说明：本系列共6篇文章，涵盖30道经典算法母题，使用Java实现
适用场景：算法学习、面试准备、编程能力提升
📋 30道算法母题总览
第1篇：数组与字符串基础（1-5）
- 两数之和
- 三数之和
- 盛最多水的容器
- 接雨水
- 最长无重复字符子串
第2篇：链表操作（6-10）
- 反转链表
- 合并两个有序链表
- 链表中倒数第k个节点
- 判断链表是否有环
- 合并K个有序链表
第3篇：栈与队列（11-15）⭐ 本篇
- 有效的括号
- 用栈实现队列
- 最小栈
- 滑动窗口最大值
- 每日温度
第4篇：二叉树遍历（16-20）
- 二叉树的前序遍历
- 二叉树的中序遍历
- 二叉树的后序遍历
- 二叉树的层序遍历
- 二叉树的最大深度
第5篇：动态规划（21-25）
- 爬楼梯
- 最长递增子序列
- 最长公共子序列
- 背包问题（0-1背包）
- 编辑距离
第6篇：搜索与排序（26-30）
- 二分查找
- 快速排序
- 归并排序
- 岛屿数量（DFS/BFS）
- 全排列（回溯）
第11题：有效的括号
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
- 每个右括号都有一个对应的相同类型的左括号
示例：
输入：s = "()"
输出：true
输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false
输入：s = "([)]"
输出：false
输入：s = "{[]}"
输出：true
💡 解题思路
栈的应用：
- 遍历字符串中的每个字符
- 如果是左括号，压入栈中
- 如果是右括号：
- 检查栈是否为空（空则无效）
- 弹出栈顶元素，检查是否匹配
- 不匹配则返回 false
- 遍历结束后，检查栈是否为空（空则有效）
日常应用
- 代码编辑器：括号匹配检查
- HTML/XML 解析：标签配对验证
- 数学表达式：公式合法性检查
- 编译器：语法分析的基础
🔧 代码解决的问题
- 括号配对验证
- 嵌套结构的合法性检查
- 字符串的语法验证
💻 Java实现代码
import java.util.Stack;
public class ValidParentheses {
/**
* 有效的括号 - 栈
* @param s 括号字符串
* @return 是否有效
*/
public boolean isValid(String s) {
// 奇数长度的字符串必然无效
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
// 左括号入栈
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
}
// 右括号匹配
else {
// 栈为空，说明没有对应的左括号
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
// 检查是否匹配
if (c == ')' && top != '(') return false;
if (c == ']' && top != '[') return false;
if (c == '}' && top != '{') return false;
}
}
// 栈为空说明所有括号都匹配
return stack.isEmpty();
}
/**
* 优化的版本 - 使用 HashMap
*/
public boolean isValidOptimized(String s) {
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
// 右括号到左括号的映射
java.util.Map<Character, Character> map = new java.util.HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
// 右括号
if (stack.isEmpty() || stack.pop() != map.get(c)) {
return false;
}
} else {
// 左括号
stack.push(c);
}
}
return stack.isEmpty();
}
// 测试方法
public static void main(String[] args) {
ValidParentheses solution = new ValidParentheses();
String[] testCases = {"()", "()[]{}", "(]", "([)]", "{[]}"};
boolean[] expected = {true, true, false, false, true};
for (int i = 0; i < testCases.length; i++) {
boolean result = solution.isValid(testCases[i]);
System.out.println("输入: \"" + testCases[i] + "\"");
System.out.println("输出: " + result + " (期望: " + expected[i] + ")");
System.out.println();
}
}
}
⏱️ 复杂度分析
-
时间复杂度：O(n)
- n 是字符串的长度
- 遍历一次字符串，每次栈操作为 O(1)
-
空间复杂度：O(n)
- 最坏情况下，所有字符都是左括号
- 栈的深度为 n
第12题：用栈实现队列
📝 题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。
示例：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2]
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
💡 解题思路
双栈法：
- 使用两个栈：
stackIn（入队栈）和stackOut（出队栈） - push 操作：直接压入
stackIn - pop/peek 操作：
- 如果
stackOut为空，将stackIn的所有元素倒入stackOut - 从
stackOut弹出/查看栈顶元素
- 如果
- empty 操作：两个栈都为空时队列为空
核心思想：
stackIn负责接收新元素（后进）stackOut负责提供旧元素（先出）- 元素从
stackIn转移到stackOut时，顺序反转，实现 FIFO
日常应用
- 消息队列：缓冲和处理消息
- 任务调度：按顺序处理任务
- 打印队列：文档按提交顺序打印
- 数据流处理：先进先出的数据处理
🔧 代码解决的问题
- 用 LIFO 结构实现 FIFO
- 摊还分析（Amortized Analysis）
- 数据结构的设计模式
💻 Java实现代码
import java.util.Stack;
class MyQueue {
private Stack<Integer> stackIn;
private Stack<Integer> stackOut;
/** Initialize your data structure here. */
public MyQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
stackIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
// 如果 stackOut 为空，转移元素
if (stackOut.isEmpty()) {
transferElements();
}
return stackOut.pop();
}
/** Get the front element. */
public int peek() {
// 如果 stackOut 为空，转移元素
if (stackOut.isEmpty()) {
transferElements();
}
return stackOut.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
/** 将 stackIn 的元素转移到 stackOut */
private void transferElements() {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
// 测试方法
public static void main(String[] args) {
MyQueue queue = new MyQueue();
queue.push(1);
System.out.println("push(1)");
queue.push(2);
System.out.println("push(2)");
System.out.println("peek(): " + queue.peek()); // 返回 1
System.out.println("pop(): " + queue.pop()); // 返回 1
System.out.println("empty(): " + queue.empty()); // 返回 false
System.out.println("pop(): " + queue.pop()); // 返回 2
System.out.println("empty(): " + queue.empty()); // 返回 true
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
⏱️ 复杂度分析
时间复杂度：
- push：O(1) - 直接压栈
- pop：摊还 O(1) - 每个元素最多入栈和出栈两次
- peek：摊还 O(1) - 同 pop
- empty：O(1) - 检查两个栈
空间复杂度：O(n)
- 两个栈总共存储 n 个元素
第13题：最小栈
📝 题目描述
设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中pop()—— 删除栈顶的元素top()—— 获取栈顶元素getMin()—— 检索栈中的最小元素
示例：
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3
minStack.pop();
minStack.top(); --> 返回 0
minStack.getMin(); --> 返回 -2
💡 解题思路
辅助栈法：
- 使用两个栈：
dataStack（数据栈）和minStack（最小值栈） - push 操作：
- 元素压入
dataStack - 如果
minStack为空或新元素 ≤ 当前最小值，也压入minStack
- 元素压入
- pop 操作：
- 从
dataStack弹出元素 - 如果弹出的元素等于
minStack的栈顶，也弹出minStack
- 从
- getMin 操作：返回
minStack的栈顶元素
关键点：
minStack的栈顶始终是当前数据栈的最小值- 相等元素也要压入
minStack（处理重复最小值）
🎯 日常应用
- 股票交易：记录最低价格
- 游戏开发：跟踪最低分数
- 监控系统：记录最小指标值
- 算法优化：需要频繁查询最小值的场景
🔧 代码解决的问题
- O(1) 时间获取最小值
- 空间优化的技巧
- 栈的扩展应用
Java实现代码
import java.util.Stack;
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
/** Initialize your data structure here. */
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
}
/** Push element x onto stack. */
public void push(int val) {
dataStack.push(val);
// 如果 minStack 为空或新元素小于等于当前最小值
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
/** Removes the element on top of the stack. */
public void pop() {
if (dataStack.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
int popped = dataStack.pop();
// 如果弹出的元素是最小值，也要弹出 minStack
if (popped == minStack.peek()) {
minStack.pop();
}
}
/** Get the top element. */
public int top() {
if (dataStack.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return dataStack.peek();
}
/** Retrieve the minimum element in the stack. */
public int getMin() {
if (minStack.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return minStack.peek();
}
// 测试方法
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(-2);
System.out.println("push(-2)");
minStack.push(0);
System.out.println("push(0)");
minStack.push(-3);
System.out.println("push(-3)");
System.out.println("getMin(): " + minStack.getMin()); // -3
System.out.println("top(): " + minStack.top()); // -3
minStack.pop();
System.out.println("pop()");
System.out.println("getMin(): " + minStack.getMin()); // -2
System.out.println("top(): " + minStack.top()); // 0
}
}
/**
* 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();
*/
⏱️ 复杂度分析
-
时间复杂度：
- push：O(1)
- pop：O(1)
- top：O(1)
- getMin：O(1)
-
空间复杂度：O(n)
- 最坏情况下，所有元素都压入
minStack（递减序列） - 最好情况下，只有最小值压入
minStack（递增序列）
- 最坏情况下，所有元素都压入
第14题：滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
💡 解题思路
单调队列（双端队列）：
- 维护一个双端队列
deque，存储元素的索引 - 队列中的元素对应的值从大到小排列（单调递减）
- 遍历数组：
- 移除队列中超出窗口范围的索引（队首）
- 移除队列中小于当前元素的索引（队尾），保持单调性
- 将当前元素索引加入队尾
- 当窗口形成后（i >= k-1），队首就是最大值
为什么用单调队列？
- 队首始终是最大值
- 被遮挡的小元素永远不会成为最大值，可以直接丢弃
- 时间复杂度从 O(nk) 优化到 O(n)
日常应用
- 股票分析：滑动窗口内的最高价
- 信号处理：峰值检测
- 图像处理：局部最大值提取
- 性能监控：时间段内的峰值指标
🔧 代码解决的问题
- 窗口内的极值查询
- 避免重复比较
- 线性时间复杂度的优化
💻 Java实现代码
import java.util.Deque;
import java.util.LinkedList;
public class SlidingWindowMaximum {
/**
* 滑动窗口最大值 - 单调队列
* @param nums 输入数组
* @param k 窗口大小
* @return 每个窗口的最大值数组
*/
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
// 双端队列，存储索引
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
// 1. 移除超出窗口范围的索引（队首）
if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// 2. 维护单调递减队列（移除队尾小于当前元素的索引）
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
// 3. 将当前元素索引加入队尾
deque.offerLast(i);
// 4. 当窗口形成后，记录最大值（队首）
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
// 测试方法
public static void main(String[] args) {
SlidingWindowMaximum solution = new SlidingWindowMaximum();
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
System.out.println("输入数组: " + java.util.Arrays.toString(nums));
System.out.println("窗口大小: " + k);
int[] result = solution.maxSlidingWindow(nums, k);
System.out.println("窗口最大值: " + java.util.Arrays.toString(result));
}
}
⏱️ 复杂度分析
-
时间复杂度：O(n)
- 每个元素最多入队和出队一次
- 均摊时间复杂度为 O(1)
-
空间复杂度：O(k)
- 双端队列最多存储 k 个元素
第15题：每日温度
题目描述
给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例：
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
解释:
第0天(73度) -> 第1天(74度) 更高，间隔1天
第1天(74度) -> 第2天(75度) 更高，间隔1天
第2天(75度) -> 第6天(76度) 更高，间隔4天
第3天(71度) -> 第5天(72度) 更高，间隔2天
...
💡 解题思路
单调栈：
- 维护一个单调栈，存储温度的索引
- 栈中温度对应的值从大到小排列（单调递减）
- 遍历温度数组：
- 如果当前温度 > 栈顶索引对应的温度：
- 弹出栈顶索引
- 计算天数差：当前索引 - 栈顶索引
- 记录结果
- 将当前索引压入栈中
- 如果当前温度 > 栈顶索引对应的温度：
- 栈中剩余的索引对应没有更高温度的天数（默认为 0）
核心思想：
- 栈中存储的是等待更高温度的天数索引
- 当遇到更高温度时，就找到了等待天的答案
🎯 日常应用
- 股票预测：找到下一个更高价格的日期
- 销售分析：预测销量增长的时间
- 天气预：温度变化趋势分析
- 排队系统：等待服务的时间预测
代码解决的问题
- "下一个更大元素"问题
- 单调栈的经典应用
- 避免暴力搜索的 O(n²) 复杂度
💻 Java实现代码
import java.util.Stack;
public class DailyTemperatures {
/**
* 每日温度 - 单调栈
* @param temperatures 温度数组
* @return 等待更高温度的天数数组
*/
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] result = new int[n];
// 单调栈，存储索引
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
// 当当前温度高于栈顶索引对应的温度时
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prevIndex = stack.pop();
result[prevIndex] = i - prevIndex;
}
// 将当前索引入栈
stack.push(i);
}
// 栈中剩余的索引对应没有更高温度的天数（默认为0，无需处理）
return result;
}
/**
* 暴力法（不推荐，仅作对比）
*/
public int[] dailyTemperaturesBruteForce(int[] temperatures) {
int n = temperatures.length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (temperatures[j] > temperatures[i]) {
result[i] = j - i;
break;
}
}
}
return result;
}
// 测试方法
public static void main(String[] args) {
DailyTemperatures solution = new DailyTemperatures();
int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
System.out.println("温度数组: " + java.util.Arrays.toString(temperatures));
int[] result = solution.dailyTemperatures(temperatures);
System.out.println("等待天数: " + java.util.Arrays.toString(result));
System.out.println("\n详细解释:");
for (int i = 0; i < temperatures.length; i++) {
System.out.printf("第%d天(%d度) -> 等待%d天\n",
i, temperatures[i], result[i]);
}
}
}
⏱️ 复杂度分析
-
时间复杂度：O(n)
- 每个元素最多入栈和出栈一次
- 均摊时间复杂度为 O(1)
-
空间复杂度：O(n)
- 栈的最大深度为 n（递减序列）
对比暴力法：
- 暴力法：O(n²) 时间复杂度
- 单调栈：O(n) 时间复杂度
- 对于大规模数据，单调栈优势明显
📊 总结与对比
栈与队列技巧总结
| 题目 | 核心技巧 | 关键数据结构 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 有效的括号 | 栈匹配 | Stack | O(n) | O(n) |
| 用栈实现队列 | 双栈转换 | 2×Stack | 摊还O(1) | O(n) |
| 最小栈 | 辅助栈 | 2×Stack | O(1) | O(n) |
| 滑动窗口最大值 | 单调队列 | Deque | O(n) | O(k) |
| 每日温度 | 单调栈 | Stack | O(n) | O(n) |
通用解题模板
1. 括号匹配模板
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (是左括号) {
stack.push(c);
} else {
if (stack.isEmpty() || !匹配) return false;
stack.pop();
}
}
return stack.isEmpty();
2. 单调栈模板（下一个更大元素）
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int prevIndex = stack.pop();
result[prevIndex] = i - prevIndex;
}
stack.push(i);
}
3. 单调队列模板（滑动窗口最大值）
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
// 移除超出窗口的元素
if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// 维护单调性
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
4. 双栈实现队列模板
class MyQueue {
Stack<Integer> stackIn, stackOut;
public void push(int x) { stackIn.push(x); }
public int pop() {
if (stackOut.isEmpty()) {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
return stackOut.pop();
}
}
📚 下一篇预告
第4篇：二叉树遍历（16-20）
- 二叉树的前序遍历
- 二叉树的中序遍历
- 二叉树的后序遍历
- 二叉树的层序遍历
- 二叉树的最大深度
如果觉得这篇文章对您有帮助，欢迎：
- 👍 点赞支持
- 💬 留言讨论
- ⭐ 收藏备用
有任何算法问题，欢迎在评论区交流！
更多推荐
6
0- 0
已为社区贡献7条内容
所有评论(0)