LeetCode 面试题 03.03. 堆盘子

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 程序员面试金典（第 6 版） 字节
标签
栈 链表 设计

题目描述

✅ 面试题 03.03. 堆盘子

image-20260929105659148

题意分析

用多个容量为 cap 的子栈保存元素。push 向最后一个子栈压入，满了才新建；pop 从最后一个子栈弹出；popAt(index) 从指定子栈弹出。子栈变空后必须移除，后面的子栈下标随之改变；不能弹出时返回 -1。

解法：数组/列表维护多个子栈

核心思路

[!blue]
外层列表保存子栈的当前顺序，内层分别维护各自的栈顶和长度。 每次操作结束后，列表中只保留非空子栈，且每个子栈的长度不超过 cap。因此最后一个子栈存在时，就一定可以作为 pop 的目标，无需向前跳过空栈。

push 先处理零容量：它无法容纳任何元素，直接忽略。容量有效时，若列表为空或最后一个子栈已满，就新建子栈，再把元素压到末尾。中间子栈因为 popAt 出现空位也不去回填，压入位置始终只由末尾子栈决定。

popAt 先检查下标是否属于当前列表，再删除该子栈的栈顶。若删除后子栈为空，就移除外层列表中的这一项，后续子栈整体前移，但不搬运它们内部的元素。普通 pop 直接调用末尾下标的 popAt，空列表时下标为 -1，也由同一边界检查返回 -1。

不能用总元素数除以容量来定位子栈：指定位置弹出后，中间子栈可能不满。必须以实际列表长度和各子栈的实际长度作为判断依据。

解题步骤

  1. 保存容量，外层列表初始为空，只有需要压入时才创建子栈。
  2. push 检查容量，再按末尾是否存在、是否已满决定要不要新建，最后压入元素。
  3. pop 将末尾下标交给 popAt；popAt 对负下标或越界下标返回 -1。
  4. 弹出指定子栈的栈顶，若它已空则删除该子栈。Go 截短子切片后要写回外层列表，后续操作才能看到更新后的长度。

代码实现

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 均摊 $O(1)$，末尾 pop 为 $O(1)$；popAt 弹空中间子栈时需移动后续引用，最坏 $O(s)$，s 为当前子栈数。
  • 空间复杂度：按外层列表及各子栈保留容量的总和计；中间子栈可能不满，不能用当前盘子数除以容量推断子栈数。

关键点总结

[!green]

  • 中间子栈不必保持满容量。
  • 删除的是空子栈，不是将后面盘子逐个补位。
  • 子栈下标以当前列表为准，删除后会变化。

易错点总结

[!yellow]

  • 容量零仍接收盘子：违反容量要求。
  • popAt 弹空后留下空子栈：后续下标语义与末尾处理不一致。
  • 只凭总盘子数计算子栈编号：中间弹出后分布已不规则。
  • Go 只截短局部子切片，不写回外层列表：下次仍看到旧长度。

相似题目

题目 难度 关联与区别
1172. 餐盘栈 困难 原题push填最左未满栈，本题push只进入最后一摞，空位与索引管理规则不能混用。
面试题 03.01. 三合一 简单 原题固定三个栈且共用一个数组，本题子栈数量可随容量需求变化。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/42495272
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！