LeetCode 1172. 餐盘栈

2023-03-22 HGNULB 约 14 分钟

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

分类

题目描述

✅ 1172. 餐盘栈

题意分析

要维护一排从左到右排列、每个容量都固定为 capacity 的栈，支持三种操作：push 把元素放进最左边尚未放满的栈；pop 从最右边非空的栈弹出栈顶；popAtStack(index) 从指定下标的栈弹出栈顶。后两个操作在没有可弹元素时返回 -1。

三个操作的方向是不对称的：push 永远看最左，pop 永远看最右，而 popAtStack 会在中间任意位置戳出一个空位。这种「一端插入、另一端删除、中间还会被打洞」的组合，说明单纯用一个下标指针记录当前工作位置是不够的——中间被打出来的洞必须能被后续的 push 重新填上，而右端被清空的栈又必须让 pop 能跳过去。

约束里最关键的一条是调用总次数达到 $2 \times 10^5$ 量级。这意味着单次操作不能是「从左往右扫一遍找第一个没满的栈」的线性做法，否则最坏是平方级；必须让「最左可插入位置」的查询降到对数甚至常数。反过来，如果某个清理动作总量是可摊还的（每个栈只会被创建一次、销毁一次），那么即使写在循环里也不会拖垮复杂度，这是设计题里非常常见的取舍点。

边界要提前想清楚：capacity == 1 时一个栈刚创建就是满的；所有栈都空时 pop 必须返回 -1 而不是越界；popAtStack 的下标可能指向根本不存在的栈；同一个下标可能被反复弹空又填满，因此任何「候选集合」都必须容忍重复与过期。

还有一个容易被忽略的语义：pop 的定义是「最右边非空栈的栈顶」，不是「最后一个栈的栈顶」。当右端堆积了一串被 popAtStack 掏空的栈时，这两个说法就不一样了。

解法：栈数组 + 小根堆

核心思路

先想最朴素的做法：用一个二维数组存所有栈，push 时从下标 0 往右扫，找到第一个 size() < capacity 的栈放进去；pop 时从右往左扫，找到第一个非空栈弹出。逻辑完全正确，但两个扫描都是 $O(s)$（s 为栈个数），在 $2 \times 10^5$ 次调用下会退化成平方级。

瓶颈非常明确，且左右两端各有一个：「最左的未满栈」查询慢，「最右的非空栈」查询慢。这两个瓶颈的性质其实不同，要分开破。

先看右端。右端之所以要扫，是因为尾部可能残留一串空栈。但空栈是没有任何信息量的——它既不影响 push（它同样可以被当作可插入位置），也不需要被 pop 看到。所以可以规定一条结构性约束：数组尾部永远不是空栈。只要每次删除元素后顺手把尾部的空栈全部弹掉，pop 就永远只需要看 stacks 的最后一个元素，$O(1)$ 解决。而这个删除动作是可摊还的：一个栈从被创建到被删除只会经历一次，总删除次数不超过总创建次数。

再看左端。左端的「最左未满栈」没法靠结构约束消掉，因为洞可以出现在任意位置。但注意到洞不是凭空出现的——只有一次成功的弹出才会制造出一个未满的栈。于是可以维护一个候选集合，每次弹出成功就把该下标丢进去，取最小值就是最左候选。「动态插入 + 取最小」正是小根堆的定义，$O(\log s)$。

麻烦在于这个集合会脏：同一个下标被弹空多次就会被重复插入；一个下标进堆后又被 push 填满；甚至它对应的栈已经被尾部清理删掉了。逐一维护这些失效项代价很高（堆不支持按值删除）。所以这里用懒删除：允许堆里存放垃圾，只在真正取用堆顶时才校验并丢弃。这个手法的正确性依赖一条不变量。

不变量：任何时刻，每一个「存在且未满」的栈下标，一定出现在堆中（堆里可以有多余的、重复的、过期的下标，但绝不会漏）。因此 cleanAvailable 把堆顶所有「越界」或「已满」的下标弹掉之后，剩下的堆顶必然是真正最左的未满栈；若堆被清空，说明当前不存在任何未满的栈，只能在末尾新建一个。

维护这条不变量只需盯住「一个栈何时会变成未满」这一个事件：要么它刚被创建（push 新建时若 capacity > 1 就立刻入堆），要么它刚被弹出过元素（pop 与 popAtStack 成功后立刻把下标入堆）。除此之外没有第三种途径，所以不变量始终成立。

解题步骤

构造函数：保存 capacity，初始化空的栈数组 stacks 和小根堆 available。之所以不预分配栈，是因为题目没给栈的数量上限，只能按需增长。

push 第一步：清理堆顶。为什么必须放在最前面？因为堆里允许有垃圾，不清理就可能把元素放进一个已满的栈，或者对一个已被删除的下标做数组访问。清理的判定条件是两条：idx >= stacks.size()（栈已被尾部清理删除）或 stacks.get(idx).size() == capacity（栈已被填满），两者都直接丢弃。

push 第二步：堆空则新建。清理后堆为空，由不变量可知当前不存在任何未满的栈，所以只能追加一个新栈。放入元素后，只有 capacity > 1 时这个新栈才仍是未满的，才需要入堆——capacity == 1 时它已经满了，入堆只会制造垃圾。

push 第三步：堆非空则填洞。堆顶就是最左未满栈，直接放入；放完若刚好达到 capacity，说明它不再是候选，弹出堆顶。这里弹出不是必须的（懒删除也能兜住），但顺手弹掉能让堆更干净。

pop：先清尾再弹。先调用 removeEmptyTail 保证尾部非空，此时若数组为空说明整个结构没有元素，返回 -1；否则最后一个栈的栈顶就是答案。弹出后该栈出现空位，把下标入堆以维持不变量；最后再清一次尾部，因为这次弹出可能把最后一个栈掏空了，不清理就会破坏「尾部非空」的结构约束。

popAtStack：先校验再弹。下标可能为负、可能越界、可能指向一个空栈，三种情况都返回 -1。弹出成功后同样把下标入堆。注意这里不做尾部清理也能保证正确性，因为下一次 pop 入口处就会清；但为了减少堆里的垃圾，让 pop 自己负责清理是更简单的分工。

以 capacity = 2，操作序列 push(1)、push(2)、push(3)、popAtStack(0)、push(4)、pop()、pop() 走一遍。

push(1)：堆空，新建栈 0 得 [[1]]；capacity = 2 > 1，下标 0 入堆，堆为 {0}。

push(2)：清理堆顶，0 有效（栈 0 大小 1 < 2）；放入得 [[1,2]]；栈 0 满了，弹出堆顶，堆为 {}。

push(3)：清理后堆空，新建栈 1 得 [[1,2],[3]]；下标 1 入堆，堆为 {1}。

popAtStack(0)：下标 0 有效且栈 0 非空，弹出 2，得 [[1],[3]]；下标 0 入堆，堆为 {0,1}。返回 2。

push(4)：清理堆顶，堆顶 0 有效（栈 0 大小 1 < 2）；放入得 [[1,4],[3]]；栈 0 满，弹出堆顶，堆为 {1}。注意这一步正是「最左优先」的体现——元素填回了中间的洞，而不是追加到右端。

pop()：清尾，尾部栈 1 非空不动；弹出栈 1 的栈顶 3，得 [[1,4],[]]；下标 1 入堆得 {1,1}；再次清尾，栈 1 为空被删除，得 [[1,4]]。返回 3。此时堆里的两个 1 都已过期。

pop()：清尾，尾部非空；弹出栈 0 的栈顶 4，得 [[1]]；下标 0 入堆得 {0,1,1}；清尾无事发生。返回 4。堆里那两个 1 会在下一次 push 的清理中因 idx >= stacks.size() 被丢弃。

代码实现

class DinnerPlates {
    private final int capacity;
    private final List<List<Integer>> stacks;
    private final PriorityQueue<Integer> available;

    public DinnerPlates(int capacity) {
        this.capacity = capacity;
        this.stacks = new ArrayList<>();
        this.available = new PriorityQueue<>();
    }

    public void push(int val) {
        cleanAvailable();

        if (available.isEmpty()) {
            List<Integer> stack = new ArrayList<>();
            stack.add(val);
            stacks.add(stack);
            if (capacity > 1) {
                available.offer(stacks.size() - 1);
            }
            return;
        }

        int idx = available.peek();
        stacks.get(idx).add(val);
        if (stacks.get(idx).size() == capacity) {
            available.poll();
        }
    }

    public int pop() {
        removeEmptyTail();
        if (stacks.isEmpty()) {
            return -1;
        }

        int idx = stacks.size() - 1;
        int val = popFromStack(idx);
        available.offer(idx);
        removeEmptyTail();
        return val;
    }

    public int popAtStack(int index) {
        if (index < 0 || index >= stacks.size() || stacks.get(index).isEmpty()) {
            return -1;
        }

        int val = popFromStack(index);
        available.offer(index);
        return val;
    }

    private void cleanAvailable() {
        // 堆里允许残留过期下标，真正使用前统一清理。
        while (!available.isEmpty()) {
            int idx = available.peek();
            if (idx < stacks.size() && stacks.get(idx).size() < capacity) {
                return;
            }
            available.poll();
        }
    }

    private void removeEmptyTail() {
        while (!stacks.isEmpty() && stacks.get(stacks.size() - 1).isEmpty()) {
            stacks.remove(stacks.size() - 1);
        }
    }

    private int popFromStack(int idx) {
        List<Integer> stack = stacks.get(idx);
        return stack.remove(stack.size() - 1);
    }
}

type DinnerPlates struct {
    capacity  int
    stacks    [][]int
    available intHeap
}

func Constructor(capacity int) DinnerPlates {
    return DinnerPlates{
        capacity:  capacity,
        stacks:    make([][]int, 0),
        available: intHeap{},
    }
}

func (d *DinnerPlates) Push(val int) {
    d.cleanAvailable()

    if d.available.Len() == 0 {
        d.stacks = append(d.stacks, []int{val})
        if d.capacity > 1 {
            heap.Push(&d.available, len(d.stacks)-1)
        }
        return
    }

    idx := d.available[0]
    d.stacks[idx] = append(d.stacks[idx], val)
    if len(d.stacks[idx]) == d.capacity {
        heap.Pop(&d.available)
    }
}

func (d *DinnerPlates) Pop() int {
    d.removeEmptyTail()
    if len(d.stacks) == 0 {
        return -1
    }

    idx := len(d.stacks) - 1
    val := d.popFromStack(idx)
    heap.Push(&d.available, idx)
    d.removeEmptyTail()
    return val
}

func (d *DinnerPlates) PopAtStack(index int) int {
    if index < 0 || index >= len(d.stacks) || len(d.stacks[index]) == 0 {
        return -1
    }

    val := d.popFromStack(index)
    heap.Push(&d.available, index)
    return val
}

func (d *DinnerPlates) cleanAvailable() {
    // 堆里允许残留过期下标，真正使用前统一清理。
    for d.available.Len() > 0 {
        idx := d.available[0]
        if idx < len(d.stacks) && len(d.stacks[idx]) < d.capacity {
            return
        }
        heap.Pop(&d.available)
    }
}

func (d *DinnerPlates) removeEmptyTail() {
    for len(d.stacks) > 0 && len(d.stacks[len(d.stacks)-1]) == 0 {
        d.stacks = d.stacks[:len(d.stacks)-1]
    }
}

func (d *DinnerPlates) popFromStack(idx int) int {
    stack := d.stacks[idx]
    val := stack[len(stack)-1]
    d.stacks[idx] = stack[:len(stack)-1]
    return val
}

type intHeap []int

func (h intHeap) Len() int {
    return len(h)
}

func (h intHeap) Less(i int, j int) bool {
    return h[i] < h[j]
}

func (h intHeap) Swap(i int, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *intHeap) Push(x any) {
    *h = append(*h, x.(int))
}

func (h *intHeap) Pop() any {
    old := *h
    idx := len(old) - 1
    val := old[idx]
    *h = old[:idx]
    return val
}

复杂度分析

时间复杂度：单次操作摊还 $O(\log s)$，s 为当前栈的数量，总调用 q 次即 $O(q \log s)$。凭什么：每次成功弹出最多向堆里插入一个下标，所以堆的总插入量是 $O(q)$，每个下标最多被懒清理弹出一次，因此所有 cleanAvailable 的循环次数总和是 $O(q)$，摊还到每次操作是常数次堆操作；removeEmptyTail 同理，每个栈只会被创建一次、删除一次，总删除量不超过总创建量 $O(q)$。

空间复杂度：$O(q)$。凭什么：栈数组里保存的是尚未被弹出的元素，最多 q 个；堆里最多堆积 $O(q)$ 个（含重复与过期的）下标，二者都以调用次数为上界。

关键点总结

面对「一端插入、另一端删除、中间会被打洞」的结构，先按操作方向拆瓶颈：能靠结构约束消掉的（尾部永不为空）就消掉，消不掉的（任意位置的洞）才上数据结构。这是设计题的通用拆解顺序。

懒删除是堆不支持按值删除时的标准替代方案：允许集合脏，把校验推迟到取用时。用它的前提是能写出「不漏」的不变量——本题就是「每个存在且未满的栈下标一定在堆里」。面试时主动说出这条不变量，比背代码有说服力得多。

判断一个写在循环里的清理动作会不会拖垮复杂度，看它的摊还总量而不是单次最坏：每个栈只被创建和销毁各一次，所以尾部清理的总代价与操作数同阶。

维护不变量时只需枚举「状态变化的入口」：本题中「栈变为未满」只有新建和弹出两个入口，逐一在入口处补上入堆动作即可，不必在每个函数里重新推导。

capacity == 1 这类退化参数要在设计阶段就单独过一遍，它常常让「新建即未满」这类隐含假设失效。

易错点总结

push 前不清理堆顶：capacity = 2 时先 push(1)、push(2) 让栈 0 满并残留下标 0 在堆里（若忘了在填满时弹出），下一次 push 会往已满的栈 0 里塞第三个元素，栈容量被击穿，后续所有 pop 顺序全错。

清理时只判「已满」不判「越界」：capacity = 2 下 push(1)、pop() 会把下标 0 入堆后又把空栈 0 删除，堆里残留 0 而 stacks 为空；再次 push 时用 stacks.get(0) 直接数组越界。

capacity == 1 时把新建的栈也入堆：新栈一创建就是满的，入堆后下次 push 若只判越界不判已满，就会往满栈里再塞一个；即使判了也是白白制造垃圾。

pop 弹出后忘记再清一次尾部：push(1) 后 pop() 会留下一个空栈在末尾，下一次 pop() 直接取最后一个栈的栈顶就会对空栈操作，抛异常或返回错误值，而正确答案应是 -1。

pop 弹出后忘记把下标入堆：capacity = 3 下 push(1)、push(2)、push(3)、pop() 之后栈 0 只剩两个元素却不在堆中，下一次 push 会新建栈 1，结果元素没有放进「最左未满栈」，pop 的返回顺序随之出错。

popAtStack 成功后忘记入堆：capacity = 2 下 push(1)、push(2)、push(3)、popAtStack(0)、push(4) 会把 4 追加到栈 1 而不是填回栈 0 的空位，最终 pop 返回 4 而正确答案是 3。

popAtStack 漏判 index < 0 或栈为空：负下标在 Go 里直接 panic、在 Java 里抛 IndexOutOfBoundsException；对空栈弹出则会取到 size() - 1 == -1 的位置，同样越界，而题目要求返回 -1。

把 pop 理解成「最后一个栈的栈顶」而不清尾：capacity = 1 下 push(1)、push(2)、popAtStack(1) 后末尾是空栈，pop() 应返回 1，不清尾的实现会返回 -1。

用「记录最左空位指针」代替堆：capacity = 2 下 popAtStack(5) 再 popAtStack(2)，空位出现的顺序与下标顺序相反，单个指针只能记住一个位置，必然漏掉更靠左的洞。

用有序集合并试图在填满时按值删除：Java 的 PriorityQueue.remove(Object) 是 $O(s)$ 线性扫描，在 $2 \times 10^5$ 次调用下会退化成平方级超时；要么改用 TreeSet 保证下标唯一，要么就老老实实走懒删除。

相似题目

题目	难度	考察点
716. 最大栈	困难	同样需要「按值定位并删除中间元素」，用双向链表 + 有序表替代懒删除
895. 最大频率栈	困难	也是多栈结构，但分桶依据是出现频率而非下标，不需要最左优先
155. 最小栈	中等	单栈上附加最小值信息，靠辅助栈同步压弹，不涉及跨栈的位置选择
1381. 设计一个支持增量操作的栈	中等	同为栈的设计题，难点在把区间加法差分到栈底延迟生效
295. 数据流的中位数	困难	双堆对顶维护中位数，堆用于取极值而非定位下标，无需懒删除
380. O(1) 时间插入、删除和获取随机元素	中等	用「尾部元素填洞」而不是懒删除来解决数组中间删除，是本题的对照解法
146. LRU 缓存	中等	哈希表 + 双向链表实现 $O(1)$ 的任意位置删除，正面回避了堆的删除难题
1206. 设计跳表	困难	同为有序结构的设计题，靠多级索引而非堆把定位降到 $O(\log n)$