LeetCode 716. 最大栈

2025-12-24 HGNULB 约 6 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 716. 最大栈

题意分析

设计一个栈，除了常规的压栈、弹栈、看栈顶之外，还要支持两个与最大值有关的操作：peekMax 返回当前栈中的最大值但不删除，popMax 删除并返回当前最大值。题目额外规定，当最大值出现多次时，popMax 必须删除最靠近栈顶的那一个。

这条「多个最大值取最靠近栈顶」的规定不是可有可无的措辞，它直接决定了实现的正确性。因为删除不同位置的最大值，会留下不同的剩余栈，后续的 top 和 pop 结果随之不同。任何「记录最大值出现在哪一层」的方案，都必须保证记的是最靠上的那一层。

更本质的难点在于 popMax 要删除的元素可能位于栈的中间，而栈这种结构天然只暴露一端。所以这道题的核心矛盾是：既要保持后进先出的语义，又要支持一次中间删除。识别出这个矛盾，就知道要么付出把上方元素搬开的代价，要么换一个允许原地摘除节点的底层结构。

边界情形：题目保证 pop、top、peekMax、popMax 只在栈非空时被调用，因此不必设计空栈的异常路径；元素可以是负数，所以不能用 0 之类的值当「无最大值」的哨兵。

解法：主栈 + 最大值栈 + 临时缓冲

核心思路

用主栈保存元素，再用等长的 maxStack 保存每一层对应的前缀最大值。若主栈前 $i$ 层元素已经确定，第 $i$ 层最大值只需取“上一层最大值”和“新元素”的较大者。

核心不变量是：两个栈长度始终相同，且 maxStack 的栈顶等于主栈当前最大值。push 时两边各压一层，pop 时两边各弹一层，因此 top 与 peekMax 都能 $O(1)$ 完成。

popMax 要删除的最大值可能在栈中间。先记住当前最大值，再从栈顶向下把非目标元素暂存到缓冲栈；遇到的第一个最大值必然是最靠近栈顶的那个。删除它后，把缓冲元素通过 push 压回，既恢复原顺序，也重新建立每层最大值。

这套实现选择代码短、稳定的双栈方案，代价是 popMax 最坏为线性。若追问所有修改操作都做到对数时间，可使用“双向链表 + 有序映射”：链表维护栈顺序，有序映射将每个值映射到该值节点栈，最大键给出最大值，节点可在 $O(1)$ 内摘除。

解题步骤

push(x)：主栈压入 x；最大值栈压入 max(x, 当前最大值)。

pop()：两个栈同步弹出，返回主栈元素。

top()：返回主栈顶。

peekMax()：返回最大值栈顶。

popMax()：先保存 peekMax()，再把目标值上方的元素逐个 pop 到缓冲栈。

删除首次遇到的目标值，再按缓冲栈的弹出顺序逐个 push 回主栈。

对栈 [5, 1, 5]（右侧为栈顶），popMax 直接删除顶部 5；对 [5, 1]，先暂存 1、删除 5，再压回 1，最终只剩 [1]。两种情况都删除了最靠近栈顶的最大值。

代码实现

import java.util.*;

class MaxStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> maxStack = new ArrayDeque<>();

    public void push(int x) {
        stack.push(x);
        int max = maxStack.isEmpty() ? x : Math.max(x, maxStack.peek());
        maxStack.push(max);
    }

    public int pop() {
        maxStack.pop();
        return stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return maxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Deque<Integer> buffer = new ArrayDeque<>();

        while (top() != max) {
            buffer.push(pop());
        }
        pop();

        while (!buffer.isEmpty()) {
            push(buffer.pop());
        }
        return max;
    }
}

type MaxStack struct {
    stack    []int
    maxStack []int
}

func Constructor() MaxStack {
    return MaxStack{}
}

func (this *MaxStack) Push(x int) {
    maxValue := x
    if n := len(this.maxStack); n > 0 && this.maxStack[n-1] > maxValue {
        maxValue = this.maxStack[n-1]
    }
    this.stack = append(this.stack, x)
    this.maxStack = append(this.maxStack, maxValue)
}

func (this *MaxStack) Pop() int {
    last := len(this.stack) - 1
    value := this.stack[last]
    this.stack = this.stack[:last]
    this.maxStack = this.maxStack[:last]
    return value
}

func (this *MaxStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MaxStack) PeekMax() int {
    return this.maxStack[len(this.maxStack)-1]
}

func (this *MaxStack) PopMax() int {
    maxValue := this.PeekMax()
    buffer := make([]int, 0)

    for this.Top() != maxValue {
        buffer = append(buffer, this.Pop())
    }
    this.Pop()

    for i := len(buffer) - 1; i >= 0; i-- {
        this.Push(buffer[i])
    }
    return maxValue
}

复杂度分析

时间复杂度：push、pop、top、peekMax 均为 $O(1)$。若目标最大值上方有 $t$ 个元素，popMax 需要搬出并放回它们，复杂度为 $O(t)$，最坏 $O(n)$。

空间复杂度：最大值栈长期占用 $O(n)$；popMax 的临时缓冲最坏也为 $O(n)$，合计仍为 $O(n)$。

进阶方案：双向链表摘除节点为 $O(1)$，有序映射查找或更新最大键为 $O(\log d)$，其中 $d$ 是不同值数量；因此 top 为 $O(1)$，其余修改和最大值操作为 $O(\log d)$。

关键点总结

最大值栈必须与主栈逐层对齐，即使最大值没变也要重复压入。

从栈顶向下遇到的第一个最大值，就是题目要求删除的“最靠近栈顶者”。

搬出和压回各反转一次，剩余元素的相对顺序不变。

压回时复用 push，不要手工修改两个底层栈，否则容易破坏不变量。

面试时应主动说明该实现的 popMax 是 $O(n)$，并能讲出链表加有序映射的优化方向。

易错点总结

最大值栈只在出现更大值时压入，会失去与主栈的一一对应关系。

pop 只弹主栈，最大值栈会残留已删除元素的历史最大值。

popMax 搬运前没有先保存最大值，过程中 peekMax 会随弹栈改变。

从栈底寻找最大值，或删除最大值的最早出现位置，不符合“最靠近栈顶”。

缓冲元素按错误方向压回，会把被搬出的那一段顺序反转。

压回时直接写主栈而不调用 push，会漏掉最大值栈的重建。

把所有操作都写成 $O(1)$；本解法的 popMax 明确存在最坏线性搬运。

相似题目

题目	难度	考察点
155. 最小栈	中等	只需查询最小值，无需删除中间元素
剑指 Offer 30. 包含min函数的栈	简单	与 155 同题，可练习不额外开栈的差值压缩写法
面试题 03.02. 栈的最小值	简单	同一模型换编号，接口命名略有差异
895. 最大频率栈	困难	按出现频率而非数值取最大，用分层栈实现
232. 用栈实现队列	简单	同样靠双栈搬运，摊还分析是核心考点
146. LRU 缓存	中等	双向链表加哈希表，正是本题进阶解法的同款组合