栈结构实战：从「有效括号」到「最小栈」，吃透栈的核心用法

目录一、入门必刷LeetCode 20. 有效的括号题目描述解题思路代码实现Java复杂度分析二、进阶挑战LeetCode 155. 最小栈题目描述解题思路代码实现Java复杂度分析三、两道题的核心思想总结栈作为一种 “后进先出LIFO” 的数据结构看似简单却是算法题里的常客。今天我们就通过两道经典题 ——「有效括号」和「最小栈」把栈的核心思想和应用场景讲透看完你就能直接上手写代码。一、入门必刷LeetCode 20. 有效的括号这是一道几乎所有栈入门都会遇到的题目也是面试中的高频题非常适合理解栈的核心特性。题目描述给定一个只包括(){}[]的字符串s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。解题思路这道题的核心逻辑完美契合了栈 “后进先出” 的特性遇到左括号直接压入栈中等待后续匹配。遇到右括号需要和最近的一个未匹配的左括号配对。而栈顶元素正好就是最近的左括号。匹配失败的情况栈为空却遇到了右括号没有左括号可以匹配。栈顶的左括号类型和当前右括号不匹配。遍历结束后栈必须为空所有左括号都找到了对应的右括号。为了快速判断括号类型我们可以用一个哈希表来存储 “右括号 → 左括号” 的映射。代码实现Javajava运行public boolean isValid(String s) { // 定义右括号到左括号的映射方便匹配 MapCharacter, Character map new HashMap(); map.put(), (); map.put(}, {); map.put(], [); DequeCharacter stack new LinkedList(); for (char c : s.toCharArray()) { // 如果是右括号 if (map.containsKey(c)) { // 栈为空或栈顶元素不匹配直接返回false if (stack.isEmpty() || stack.peek() ! map.get(c)) { return false; } // 匹配成功弹出栈顶元素 stack.pop(); } else { // 如果是左括号直接入栈 stack.push(c); } } // 遍历结束栈必须为空 return stack.isEmpty(); }复杂度分析时间复杂度O (n)其中 n 是字符串的长度我们只需遍历一次字符串。空间复杂度O (n)最坏情况下所有字符都是左括号需要将所有字符压入栈中。二、进阶挑战LeetCode 155. 最小栈这道题是栈的经典扩展它要求我们在实现常规栈功能的同时支持在常数时间内获取栈中的最小元素。题目描述设计一个支持pushpoptop操作并能在常数时间内检索到最小元素的栈。实现MinStack类MinStack()初始化堆栈对象。void push(int val)将元素 val 推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。解题思路这道题的难点在于如何在O(1)时间内获取最小值。如果每次都遍历栈来查找最小值时间复杂度会退化为 O (n)无法满足题目要求。最经典的解法是使用双栈主栈dataStack用来正常存储所有元素实现push、pop、top等常规操作。辅助栈minStack用来存储 “当前栈中的最小值”。每次主栈压入一个新元素时辅助栈也压入当前的最小值每次主栈弹出元素时辅助栈也同步弹出。这样getMin()方法只需要直接返回辅助栈的栈顶元素即可时间复杂度为 O (1)。代码实现Javajava运行class MinStack { // 主栈存储所有元素 private DequeInteger dataStack; // 辅助栈存储当前的最小值 private DequeInteger minStack; public MinStack() { dataStack new LinkedList(); minStack new LinkedList(); } public void push(int val) { dataStack.push(val); // 辅助栈为空或新元素小于等于当前最小值压入新元素 if (minStack.isEmpty() || val minStack.peek()) { minStack.push(val); } else { // 否则重复压入当前最小值保持两栈同步 minStack.push(minStack.peek()); } } public void pop() { // 两栈同步弹出 dataStack.pop(); minStack.pop(); } public int top() { return dataStack.peek(); } public int getMin() { // 直接返回辅助栈栈顶元素 return minStack.peek(); } }复杂度分析时间复杂度所有操作push、pop、top、getMin均为 O (1)。空间复杂度O (n)我们使用了两个栈在最坏情况下需要存储 2n 个元素。三、两道题的核心思想总结这两道题从不同角度展现了栈的应用有效括号利用栈 “后进先出” 的特性处理需要按顺序匹配的场景比如括号匹配、HTML 标签闭合等。最小栈利用 “双栈同步” 的思想在保留常规栈功能的同时扩展出了高效获取最小值的能力这是一种非常经典的空间换时间的优化思路。