LeetCode 面试题 03.03. 堆盘子
目录
题目描述
题意分析
要实现一个"看起来像一个栈、内部是多摞盘子"的数据结构。每摞盘子最多放
cap个，push时若当前最后一摞已满就另起一摞；pop从最后一摞的顶部拿；额外还有popAt(index)直接从第index摞的顶部拿。从外部看，push/pop的行为必须和普通栈完全一致。
约束里有两个必须读出来的信号。第一，
cap可能为 0，此时任何push都应该被忽略，后续所有pop/popAt返回-1；这个退化情况官方用例里是有的，不做特判会在建摞时陷入"永远满、无限新建"的怪圈。第二，popAt会在中间挖洞，这是整题的难点来源：一旦某摞被掏空，后面所有摞的下标是否要前移，直接决定了popAt的语义。
边界上还要覆盖：结构完全为空时
pop返回-1；popAt的index越界返回-1；popAt恰好掏空最后一摞；以及连续popAt(0)把前面的摞一个个删掉。题目并不要求把后面的盘子"往前挪"来填补空洞——只要求把空掉的那一摞整体移除，这是本题被普遍接受的处理方式。
解法：数组/列表维护多个子栈
核心思路
最先想到的是"用一个大数组存所有盘子，再靠算术下标
i / cap换算出它属于第几摞"。瓶颈立刻出现在popAt上：从中间摞拿走一个盘子后，这个大数组就出现了空洞，后面元素的"第几摞第几个"全部错位，要么整体搬移（$O(n)$ 且实现繁琐），要么额外维护每摞的真实长度——那还不如一开始就把每摞独立存。
于是换成显式的二维结构：外层是一个可变长列表
stacks，每个元素是一摞盘子（内层是一个栈）。这样每摞的长度天然独立，popAt只影响它自己那一摞，不会波及别人。
由此确定要维护的不变量：
stacks中不存在空摞；除最后一摞外，前面每一摞的元素个数恰好等于cap（最后一摞的个数在1..cap之间）。前半句让"stacks的下标"和"题目说的第几摞"始终对齐，也让pop()可以无脑地去stacks的末尾拿；后半句让push只需检查最后一摞是否已满，而不必扫描全部摞去找"还有空位的那一摞"。
维持这个不变量只需要两条规则。
push：若stacks为空或最后一摞已满，先追加一个新的空摞，然后压入最后一摞——这保证了"只有最后一摞可能不满"。popAt(index)：弹出该摞栈顶后，若它变空就把整摞从stacks里删掉——这保证了"不存在空摞"。有了这两条，pop()就可以直接写成popAt(stacks.size() - 1)，两条路径共用同一份边界处理，不容易写歪。
解题步骤
- 构造函数只记录
cap，不预建任何摞。懒建摞让"空结构"的表示唯一（stacks为空），省掉"有一摞但它是空的"这种中间态；中间态越少，不变量越好维持。
push(val)先处理cap <= 0直接返回。这是必须的短路：若不拦截，后面的"最后一摞已满就新建"会因为size() == 0 == cap恒成立而每次都新建一摞空摞，既违反不变量又会无限增长。
push(val)判断"需不需要新建摞"。条件是stacks.isEmpty() || 最后一摞.size() == cap。只看最后一摞就够了，正是因为不变量保证了前面的摞全是满的——这也是为什么popAt从中间掏走一个盘子后不需要把后面的盘子往前补：题目允许中间摞不满，代价只是push不会去填这些空位，而这并不违反外部可见的栈语义。
pop()直接委托给popAt(stacks.size() - 1)。复用而不是复制一遍逻辑，好处是"越界返回 -1"和"空摞要删除"这两件事只写一遍。当stacks为空时，传入的是-1，正好被popAt的越界检查拦住返回-1，不需要额外判空。
popAt(index)先做双重合法性检查，再弹出，最后清理空摞。先查index是否落在[0, stacks.size())，再查该摞是否为空（有不变量兜底，理论上不会为空，但保留这层检查能让代码对越界调用免疫）。弹出后若该摞空了，stacks.remove(index)把它删掉，后面的摞下标整体前移——这正是题目期望的行为。
以
cap = 2，操作序列push(1) → push(2) → push(3) → popAt(0) → pop() → pop()走一遍：初始
stacks = []。push(1)：列表为空，新建一摞，stacks = [[1]]。push(2)：最后一摞有 1 个 < 2，直接压，stacks = [[1, 2]]。push(3)：最后一摞已满（2 == cap），新建一摞后压入，stacks = [[1, 2], [3]]。
popAt(0)：index = 0合法，第 0 摞栈顶是2，弹出得到2，该摞变成[1]非空，不删除，stacks = [[1], [3]]，返回2。注意此时第 0 摞只有 1 个盘子，没有满，但我们不去把3挪过来。
pop()：委托popAt(1)，第 1 摞栈顶3弹出，该摞变空，从列表中删除，stacks = [[1]]，返回3。
pop()：委托popAt(0)，弹出1，该摞变空被删除，stacks = []，返回1。若此时再调一次pop()，传入popAt(-1)被越界检查拦下，返回-1，不会崩溃。
代码实现
class StackOfPlates {
private final List<Deque<Integer>> stacks = new ArrayList<>();
private final int cap;
public StackOfPlates(int cap) {
this.cap = cap;
}
public void push(int val) {
if (cap <= 0) {
return;
}
if (stacks.isEmpty() || stacks.get(stacks.size() - 1).size() == cap) {
stacks.add(new ArrayDeque<>());
}
stacks.get(stacks.size() - 1).push(val);
}
public int pop() {
return popAt(stacks.size() - 1);
}
public int popAt(int index) {
if (index < 0 || index >= stacks.size()) {
return -1;
}
Deque<Integer> stack = stacks.get(index);
if (stack.isEmpty()) {
return -1;
}
int val = stack.pop();
if (stack.isEmpty()) {
stacks.remove(index);
}
return val;
}
}
type StackOfPlates struct {
stacks [][]int
cap int
}
func Constructor(cap int) StackOfPlates {
return StackOfPlates{cap: cap}
}
func (s *StackOfPlates) Push(val int) {
if s.cap <= 0 {
return
}
if len(s.stacks) == 0 || len(s.stacks[len(s.stacks)-1]) == s.cap {
s.stacks = append(s.stacks, []int{})
}
last := len(s.stacks) - 1
s.stacks[last] = append(s.stacks[last], val)
}
func (s *StackOfPlates) Pop() int {
return s.PopAt(len(s.stacks) - 1)
}
func (s *StackOfPlates) PopAt(index int) int {
if index < 0 || index >= len(s.stacks) {
return -1
}
stack := s.stacks[index]
if len(stack) == 0 {
return -1
}
val := stack[len(stack)-1]
s.stacks[index] = stack[:len(stack)-1]
if len(s.stacks[index]) == 0 {
s.stacks = append(s.stacks[:index], s.stacks[index+1:]...)
}
return val
}
复杂度分析
- 时间复杂度：
push与pop都是均摊 $O(1)$——只访问最后一摞的栈顶，列表尾部的追加与删除是均摊常数。popAt(index)是 $O(1)$，但当该摞被掏空需要从列表中间移除时是 $O(m)$，m为当前摞数（最坏 $O(n / cap)$）。- 空间复杂度：$O(n)$，
n为当前存放的盘子总数。由于不变量保证没有空摞、且只有最后一摞可能不满，摞的数量不超过 $\lceil n / cap \rceil + 1$，没有额外浪费。
关键点总结
- "外部像一个栈、内部是多个容器"的题，先把不变量定在容器层面。本题的两条不变量——没有空摞、只有最后一摞可能不满——一旦确立，三个接口的实现几乎是被推导出来的，不需要临场想边界。
- 能复用就别复制：让
pop走popAt。两条路径共用同一份"越界返回 -1 + 清理空摞"逻辑，避免了改一处忘一处；同时stacks为空时传入-1被越界检查自然接住，省掉一次判空。- 删除中间元素后，是否要"补位"要由题意决定，不要想当然。本题不补位（中间摞允许不满），如果补位反而会让
push无法只看最后一摞，复杂度从 $O(1)$ 退化。设计题里每一个"要不要维持整齐"的选择都应该拿复杂度和题意去衡量。- 退化参数必须显式短路。
cap == 0这类参数会让"满/不满"的判断恒真，进而破坏循环或增长逻辑。凡是拿参数做容量比较的设计题，都要先问一句"这个参数取 0 或负数会怎样"。- 面试视角：主动说明
popAt的两种语义并确认。有的面试官期望"把后面的盘子往前挪以保持每摞满"，有的接受"直接删空摞"。开口前先问一句"掏空中间一摞后，后面的盘子需要前移吗"，既显示你读懂了难点，也避免写完被推翻。链表版实现（每摞用双向链表节点串起来）在需要前移时更灵活，可以作为追问的备选答案。
易错点总结
- 错误写法：
push里不判cap <= 0→ 用例cap = 0，然后push(1)：条件最后一摞.size() == cap在0 == 0时恒成立，每次 push 都新建一摞再压入，stacks变成[[1]]且这一摞已"超容量"；连续 push 会不断新建，行为完全不可预期。- 错误写法：
popAt弹出后不删除空摞 → 用例cap = 1，push(1), push(2), popAt(0), pop()：popAt(0)后第 0 摞变成空摞但仍留在列表里，pop()走到最后一摞返回2看似正确，但再pop()会落到那个空摞上返回-1，而正确答案是没有元素可弹（结构其实已空）——下标语义已经错位。- 错误写法：
pop()写成popAt(stacks.size())（漏减 1） → 用例cap = 2，push(1), pop()：stacks.size()是 1，popAt(1)越界返回-1，而正确答案是1。- 错误写法：
pop()前先判if (stacks.isEmpty()) return -1;但popAt里去掉了越界检查 → 用例直接调popAt(5)：数组下标越界抛异常。两处检查删掉任意一处都不安全，稳妥做法是把检查集中在popAt里，pop完全依赖它。- 错误写法：Java 里
stacks.remove(index)但index声明成Integer→ 用例popAt(0)：remove(Object)重载被选中，按值查找一个等于0的元素，找不到就什么也不删，空摞永远留在列表里。必须保证参数是基本类型int。- 错误写法：
popAt里先判空摞再取stacks.get(index)，但把两个检查的顺序写反 → 用例popAt(-1)：先执行stacks.get(-1)抛IndexOutOfBoundsException。越界检查必须在任何下标访问之前。- 错误写法：Go 里
Push用值接收者func (s StackOfPlates) Push(val int)→ 用例push(1), pop()：Push修改的是结构体副本，主对象的stacks始终为空，pop()返回-1。- 错误写法：Go 里删除中间摞写成
s.stacks = append(s.stacks[:index], s.stacks[index+1:])（漏了...） → 编译报错，类型不匹配：append的可变参数需要展开切片。- 错误写法：Go 里
PopAt直接stack = stack[:len(stack)-1]却不写回s.stacks[index]→ 用例cap = 3，push(1), push(2), popAt(0), popAt(0)：局部变量stack的长度变了但底层数组和s.stacks[index]的长度没变，第二次popAt(0)仍然看到 2 个元素，返回的是已经被弹过的2。切片的长度是值语义，必须显式写回。- 错误写法：用
stacks.get(stacks.size() - 1).size() >= cap之外还额外维护一个total计数并用它算摞号 → 用例cap = 2，push(1), push(2), push(3), popAt(0), push(4)：popAt让第 0 摞变成 1 个元素，但total只知道总数是 3，按total / cap算出的摞号是 1，而实际应该压进第 1 摞的判断依赖的是"最后一摞的实际长度"。任何用总数反推分布的做法，在允许中间删除后都会失效。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1172. 餐盘栈 | 困难 | 同样是多摞盘子，但要求 push 填补最左侧空位，需要额外的有序集合 |
| 155. 最小栈 | 中等 | 单栈但要 $O(1)$ 查询最小值，靠辅助栈同步维护极值 |
| 面试题 03.04. 化栈为队 | 简单 | 用两个栈模拟另一种容器，重点在均摊分析而非容量分摞 |
| 1381. 设计一个支持增量操作的栈 | 中等 | 栈上叠加区间增量，用懒标记把批量加法降到 $O(1)$ |
| 622. 设计循环队列 | 中等 | 固定容量下靠头尾指针取模复用空间，容量满的判定是核心 |