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

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

news 2026/4/27 15:34:48

一、入门必刷：LeetCode 20. 有效的括号

题目描述

解题思路

代码实现（Java）

复杂度分析

二、进阶挑战：LeetCode 155. 最小栈

题目描述

解题思路

代码实现（Java）

复杂度分析

三、两道题的核心思想总结

栈，作为一种 “后进先出（LIFO）” 的数据结构，看似简单，却是算法题里的常客。今天，我们就通过两道经典题 ——「有效括号」和「最小栈」，把栈的核心思想和应用场景讲透，看完你就能直接上手写代码。

一、入门必刷：LeetCode 20. 有效的括号

这是一道几乎所有栈入门都会遇到的题目，也是面试中的高频题，非常适合理解栈的核心特性。

题目描述

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

解题思路

这道题的核心逻辑，完美契合了栈 “后进先出” 的特性：

遇到左括号：直接压入栈中，等待后续匹配。
遇到右括号：需要和最近的一个未匹配的左括号配对。而栈顶元素，正好就是最近的左括号。
匹配失败的情况：
1. 栈为空，却遇到了右括号（没有左括号可以匹配）。
2. 栈顶的左括号类型和当前右括号不匹配。
遍历结束后，栈必须为空（所有左括号都找到了对应的右括号）。

为了快速判断括号类型，我们可以用一个哈希表来存储 “右括号 → 左括号” 的映射。

代码实现（Java）

java

运行

public boolean isValid(String s) { // 定义右括号到左括号的映射，方便匹配 Map<Character, Character> map = new HashMap<>(); map.put(')', '('); map.put('}', '{'); map.put(']', '['); Deque<Character> 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. 最小栈

这道题是栈的经典扩展，它要求我们在实现常规栈功能的同时，支持在常数时间内获取栈中的最小元素。

题目描述

设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。

实现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)。

代码实现（Java）

java

运行

class MinStack { // 主栈：存储所有元素 private Deque<Integer> dataStack; // 辅助栈：存储当前的最小值 private Deque<Integer> 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(); } }