LeetCode 716. 最大栈
题目描述
✅ 716. 最大栈
题意分析
设计一个栈，支持压入元素、移除并返回栈顶、查看栈顶，同时支持查看最大值和移除一个最大值。若最大值重复出现，
popMax必须移除其中最靠近栈顶的一次，其他元素之间的顺序保持不变。这需要同时维护两种顺序：按入栈先后找栈顶，按数值大小找最大值。查看最大值和删除最大值的难度不同；删除发生在栈中间时，还要让之后的普通栈操作保持正确。下面先给出容易理解的双栈方法，再给出避免线性搬运的索引堆方法；访问和删除操作以栈非空为前提。
解法一：主栈 + 最大值栈 + 临时缓冲
核心思路
[!blue]
主栈保存实际元素，最大值栈与它保持等长。最大值栈的每一层记录主栈从底部到这一层的最大值，而不是只记录当前元素。压入
x时，新一层最大值是x与旧最大值中的较大者；普通弹栈时两栈同时弹出，上一层记录便自动恢复为剩余栈的最大值。
top读取主栈顶部，peekMax读取最大值栈顶部，都是常量时间。但最大值可能不在主栈顶部，不能直接删除；需要先把它上面的元素暂存到缓冲栈中。从顶部不断弹出，第一次遇到的最大值就是重复最大值中最靠近栈顶的那一个。移除它之后，将缓冲中的元素按弹出的逆序重新压回主栈，这样剩余元素的原相对顺序不变。恢复时统一调用
push，也同步重建对应层的最大值记录。如果最大值位于很深的位置，一次
popMax就要搬走并放回很多元素，所以这种方法的删除最大值操作最坏仍是线性时间。它解决了功能问题；需要对数级删除时，使用下一种方法。
解题步骤
push(x)：将x压入主栈，把新前缀最大值压入最大值栈。pop()：两栈同步移除顶部一层，返回主栈弹出的值。top()和peekMax()：分别读取两栈顶部。popMax()：先读取最大值，用缓冲栈暂存目标上方元素，删除首次遇到的最大值，再逆序调用push恢复缓冲元素。
代码实现
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均摊为 $O(1)$，pop、top、peekMax为 $O(1)$；popMax为 $O(t + 1)$，其中t是目标上方元素数，最坏为 $O(n)$。- 空间复杂度：$O(n)$，用于主栈、等长最大值栈以及删除时的临时缓冲。
关键点总结
[!green]
- 最大值栈保存每一层的前缀最大值，两栈逐层对应，普通弹栈时才能直接恢复旧最大值。
- 从顶部首次遇到最大值便删除，天然满足重复值的栈顶优先规则。
- 缓冲逆序恢复保证剩余元素次序，复用
push保证最大值记录同步恢复。
解法二：双向链表 + 索引大根堆
核心思路
[!blue]
要直接删除栈中间的节点，需要知道它在栈顺序中的前驱和后继，因此用双向链表保存入栈顺序，尾节点就是栈顶。再用大根堆按数值维护所有元素，堆顶就是要删除的最大值。链表与堆保存同一个节点对象，分别负责位置顺序和数值顺序。
节点保存
value、递增的入栈序号order、链表前后指针以及当前堆下标index。堆比较先看值，大值优先；值相同时看序号，后入栈者优先。删除不会改变存活节点的相对入栈顺序，因此序号较大的同值节点仍是更靠近栈顶的那个。普通
pop直接找到链表尾节点，利用它的index从堆中删除，再从链表摘下；popMax直接找到堆顶，删除堆顶并从链表摘下同一个节点。这样无论通过哪种顺序找到目标，都能同步维护另一种顺序，不需要搜索或搬运中间元素。堆中任意位置的删除，先把末尾节点换到空缺处并缩短堆。新节点若比父节点优先级高，就向上调整；否则父边已经合法，只需要检查是否应向下调整。每次交换都必须同步两个节点的
index，保证后续普通弹栈仍能直接找到正确堆位置。Java 显式实现这套过程，Go 使用container/heap完成调整，并在接口的Swap中更新索引。链表摘除只需连接目标的前驱和后继；删除尾节点时，还要把
tail移到前驱。头部哨兵不对应真实元素，也不进入堆，它只是让删除首个真实节点时同样拥有可连接的前驱。每次操作结束后，堆与链表中的存活节点完全一致，区别仅在排序方式；这条一致性，加上堆的比较规则和实时索引，保证两种删除及两种查询都能正确工作。
解题步骤
- 初始化空堆和链表头哨兵，令
tail指向哨兵，入栈序号从零开始递增。- 压栈时创建节点，追加到链表尾部，同时加入堆并上浮；比较规则为先按值、再按入栈序号从大到小。
- 普通弹栈时取
tail，按节点保存的堆下标删除对应项，再从链表摘除并返回值。- 删除最大值时取堆顶，完成堆删除后从链表摘除同一节点，返回其值。
- 查看栈顶直接读取
tail.value，查看最大值直接读取堆顶；所有堆交换同步维护节点索引。
代码实现
class MaxStack {
private static class Node {
int value;
int index;
long order;
Node prev;
Node next;
Node(int value, long order) {
this.value = value;
this.order = order;
}
}
private final List<Node> heap = new ArrayList<>();
private Node tail = new Node(0, -1);
private long sequence;
public void push(int x) {
Node node = new Node(x, sequence++);
// 同一个节点同时进入链表和堆，两种顺序共享成员身份
node.prev = tail;
tail.next = node;
tail = node;
node.index = heap.size();
heap.add(node);
up(node.index);
}
public int top() {
return tail.value;
}
public int peekMax() {
return heap.get(0).value;
}
public int pop() {
Node node = tail;
removeAt(node.index);
unlink(node);
return node.value;
}
public int popMax() {
Node node = heap.get(0);
removeAt(0);
unlink(node);
return node.value;
}
private void unlink(Node node) {
node.prev.next = node.next;
if (node.next == null) {
tail = node.prev;
} else {
node.next.prev = node.prev;
}
}
private boolean higher(Node a, Node b) {
// 同值时新插入者更靠近栈顶，必须优先删除
return a.value > b.value || (a.value == b.value && a.order > b.order);
}
private void swap(int i, int j) {
Node a = heap.get(i);
Node b = heap.get(j);
heap.set(i, b);
heap.set(j, a);
// 交换后同步修复索引，普通弹栈才能直接定位堆内节点
b.index = i;
a.index = j;
}
private void removeAt(int index) {
int last = heap.size() - 1;
swap(index, last);
heap.remove(last);
if (index == last) {
return;
}
// 尾节点补洞后可能破坏父边或孩子边，按实际方向修复
if (index > 0 && higher(heap.get(index), heap.get((index - 1) / 2))) {
up(index);
} else {
down(index);
}
}
private void up(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (!higher(heap.get(index), heap.get(parent))) {
break;
}
swap(index, parent);
index = parent;
}
}
private void down(int index) {
while (index * 2 + 1 < heap.size()) {
int child = index * 2 + 1;
if (child + 1 < heap.size() && higher(heap.get(child + 1), heap.get(child))) {
child++;
}
if (!higher(heap.get(child), heap.get(index))) {
break;
}
swap(index, child);
index = child;
}
}
}
import "container/heap"
type stackNode struct {
value, index int
order int64
prev, next *stackNode
}
type nodeHeap []*stackNode
func (h nodeHeap) Len() int { return len(h) }
func (h nodeHeap) Less(i, j int) bool {
// 同值时序号更大者更靠近栈顶，先删除它
return h[i].value > h[j].value ||
(h[i].value == h[j].value && h[i].order > h[j].order)
}
func (h nodeHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
// 堆调整必须同步索引，后续才能直接删除链表中的指定节点
h[i].index, h[j].index = i, j
}
func (h *nodeHeap) Push(x any) {
node := x.(*stackNode)
node.index = len(*h)
*h = append(*h, node)
}
func (h *nodeHeap) Pop() any {
old := *h
last := len(old) - 1
node := old[last]
old[last] = nil
*h = old[:last]
return node
}
type MaxStack struct {
tail *stackNode
nodes nodeHeap
sequence int64
}
func Constructor() MaxStack {
return MaxStack{tail: &stackNode{}}
}
func (s *MaxStack) Push(x int) {
node := &stackNode{value: x, order: s.sequence, prev: s.tail}
s.sequence++
// 链表和堆保存同一个节点，删除时同时更新两侧
s.tail.next = node
s.tail = node
heap.Push(&s.nodes, node)
}
func (s *MaxStack) Top() int { return s.tail.value }
func (s *MaxStack) PeekMax() int { return s.nodes[0].value }
func (s *MaxStack) Pop() int {
node := s.tail
// 利用节点索引删除堆内项，无需遍历查找
heap.Remove(&s.nodes, node.index)
s.unlink(node)
return node.value
}
func (s *MaxStack) PopMax() int {
node := heap.Pop(&s.nodes).(*stackNode)
s.unlink(node)
return node.value
}
func (s *MaxStack) unlink(node *stackNode) {
node.prev.next = node.next
if node.next == nil {
s.tail = node.prev
} else {
node.next.prev = node.prev
}
}
复杂度分析
- 时间复杂度：
top、peekMax为 $O(1)$；pop、popMax为 $O(\log(n + 1))$；push均摊为 $O(\log(n + 1))$。链表操作为常量时间，主要开销是沿堆的一条路径调整，压入还包含动态数组的均摊扩容成本。- 空间复杂度：$O(n)$，保存节点、链表连接和堆数组。不采用延迟删除，因此不会另行积累等待清理的已删除节点。
关键点总结
[!green]
- 链表尾部定位栈顶，堆顶定位最大值，同一节点对象连接两种顺序。
- 入栈序号负责重复最大值的选择，堆下标负责从指定节点快速删除，两者不能混淆。
- 任意堆位置删除后，末项补洞可能需要上浮或下沉，每次交换都要维护索引。
- Go 堆接口的
Pop只移除末项，真正的堆顶移除和任意位置删除由heap.Pop、heap.Remove先调整后调用它完成。
易错点总结
[!yellow]
- 双栈方法只在遇到更大值时才记录最大值，会破坏当前实现的等长对应，普通弹栈就无法逐层同步。
- 恢复缓冲只修改主栈、不经过
push，最大值栈会缺少对应记录；恢复顺序不反转也会改变原栈顺序。- 把双栈的
popMax标成常量或对数时间，忽略了目标上方元素的线性搬运。- 索引堆只按值比较，会在重复最大值时选中错误的出现位置；必须让较新的节点优先。
- 堆交换后不更新索引，后续按链表尾节点删除时可能移除另一个堆元素。
- 仅从链表或堆的一侧删除，会使栈顶查询和最大值查询看到不同的成员，所有删除都必须更新两侧。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 155. 最小栈 | 中等 | 原题只需查询栈内最小值，本题还要移除最近的最大值，必须同时维护栈顺序与极值定位。 |
| 895. 最大频率栈 | 困难 | 同样按额外优先级弹出并以最近入栈打破平局，原题优先级是频率，本题是元素值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！