栈与队列：有效括号匹配、最小栈、用队列实现栈、滑动窗口最大值

栈和队列，这两个数据结构看起来简单，但面试里翻车的概率其实不低。我面过不少候选人，八股文背得滚瓜烂熟，一写代码就露馅。说白了，栈和队列考的不是你会不会用，而是你能不能在复杂场景下灵活组合它们。

今天咱们一口气拿下四个经典题：有效括号匹配、最小栈、用队列实现栈、滑动窗口最大值。每个我都会结合项目里的真实踩坑经历来讲。

1. 有效括号匹配

这题太经典了，几乎每场面试都会遇到。题目很简单：给一个只包含 (){}[] 的字符串，判断括号是否有效闭合。

核心思路就一句话：左括号入栈，右括号匹配栈顶。

我习惯用字典来存映射关系，这样代码更干净：

func isValid(_ s: String) -> Bool {
    var stack = [Character]()
    let map: [Character: Character] = [")": "(", "}": "{", "]": "["]
    
    for char in s {
        if let expected = map[char] {
            // 右括号：检查栈顶是否匹配
            if stack.isEmpty || stack.last != expected {
                return false
            }
            stack.removeLast()
        } else {
            // 左括号：直接入栈
            stack.append(char)
        }
    }
    
    return stack.isEmpty
}

关键点：最后一定要检查栈是否为空。我见过有人只匹配了右括号，忘了处理多余的左括号，比如 "(((" 这种情况。

小技巧：用 stack.last 而不是 stack[stack.count-1]，可读性更好。Swift 里 last 是 O(1) 操作，放心用。

2. 最小栈

设计一个栈，支持 push、pop、top 和 getMin，且所有操作都是 O(1)。

你想想看，如果只用一个栈，getMin 怎么做到 O(1)？最简单的办法就是用两个栈：一个存数据，一个存当前最小值。

我在项目中遇到过类似需求——实时监控系统里需要记录请求延迟的最小值。当时我直接用了一个辅助栈，代码量很少，性能也稳。

class MinStack {
    private var stack: [Int] = []
    private var minStack: [Int] = []
    
    func push(_ val: Int) {
        stack.append(val)
        // 辅助栈：如果为空或新值更小，就入栈
        if minStack.isEmpty || val <= minStack.last! {
            minStack.append(val)
        } else {
            // 否则重复当前最小值
            minStack.append(minStack.last!)
        }
    }
    
    func pop() {
        stack.removeLast()
        minStack.removeLast()
    }
    
    func top() -> Int {
        return stack.last!
    }
    
    func getMin() -> Int {
        return minStack.last!
    }
}

注意：push 时判断条件用 <= 而不是 <。为什么？如果连续 push 两个相同的最小值，pop 一个后最小值不能变。我曾经在这里吃过亏，debug 了半天才发现是等号的问题。

3. 用队列实现栈

这道题考的是数据结构的互相模拟。用两个队列实现栈，要求 push、pop、top、empty 都符合栈的 LIFO 特性。

思路其实不复杂：每次 push 新元素时，把它放到队列头部。怎么做？先把新元素入队，再把队列里之前的元素依次出队再入队，这样新元素就跑到队首了。

class MyStack {
    private var queue: [Int] = []
    
    func push(_ x: Int) {
        queue.append(x)
        // 把前面的元素移到后面
        for _ in 0..<queue.count - 1 {
            queue.append(queue.removeFirst())
        }
    }
    
    func pop() -> Int {
        return queue.removeFirst()
    }
    
    func top() -> Int {
        return queue.first!
    }
    
    func empty() -> Bool {
        return queue.isEmpty
    }
}

嗯，这里要注意：removeFirst() 在 Swift 里是 O(n) 的，因为数组需要移动元素。如果追求极致性能，可以用 LinkedList 或者 ContiguousArray。不过面试时用数组就够了，面试官更关心你的思路。

4. 滑动窗口最大值

这题是栈与队列的进阶应用。给一个数组和一个窗口大小 k，窗口每次右移一位，求每个窗口的最大值。

暴力法 O(n*k) 肯定不行。最优解是用双端队列（deque），维护一个单调递减队列。队列里存的是下标，不是值。

我当年在做一个实时行情展示模块时，就遇到了类似问题——需要快速计算最近 N 笔交易的最大价格。用双端队列，时间复杂度直接降到 O(n)。

func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
    guard !nums.isEmpty, k > 0 else { return [] }
    
    var result = [Int]()
    var deque: [Int] = [] // 存下标，保持单调递减
    
    for i in 0..<nums.count {
        // 移除超出窗口范围的元素
        if !deque.isEmpty && deque.first! < i - k + 1 {
            deque.removeFirst()
        }
        
        // 移除比当前元素小的元素（它们不可能成为最大值了）
        while !deque.isEmpty && nums[deque.last!] < nums[i] {
            deque.removeLast()
        }
        
        deque.append(i)
        
        // 当窗口形成后，记录最大值
        if i >= k - 1 {
            result.append(nums[deque.first!])
        }
    }
    
    return result
}

核心思想：双端队列里始终保持递减顺序，队首永远是当前窗口的最大值。每次移动窗口时，先淘汰过期元素，再淘汰比新元素小的元素，最后把新元素加进来。

总结对比

题目 核心数据结构 时间复杂度 空间复杂度
有效括号匹配 栈 O(n) O(n)
最小栈 双栈 O(1) 每操作 O(n)
用队列实现栈 单队列 push O(n), 其余 O(1) O(n)
滑动窗口最大值 双端队列 O(n) O(k)

这四个题，从基础到进阶，覆盖了栈和队列最常见的面试场景。我个人建议你先把前两个练熟，再挑战后两个。尤其是滑动窗口最大值，面试里出现频率很高，而且能很好地考察你对数据结构的理解深度。

记住一句话：栈擅长度量最近相关性，队列擅长顺序处理，双端队列则是两者的结合体。搞懂这个，面试时遇到变形题也不慌。

← 上一章 📖 返回目录 下一章 →