LeetCode 1172. 餐盘栈

约 9 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 字节 旷视
标签
哈希表 栈 设计 堆（优先队列）

题目描述

✅ 1172. 餐盘栈

image-20260928230212679

image-20260928230212681

image-20260928230212682

题意分析

一排栈从左到右编号，每个栈容量都是 capacity。push 必须放入最左边未满的栈，pop 必须弹出最右边非空栈的栈顶，popAtStack 只弹出指定编号的栈顶；没有可弹元素时返回 -1。

栈数组可以直接访问指定编号，末尾空栈可以裁掉后找到最右非空栈。难点在于中间弹出产生的空位也要优先填回，因此再用小根堆维护可能未满的栈下标，快速取得最左候选。

解法：栈数组 + 小根堆

核心思路

[!blue]

stacks[i] 保存编号为 i 的栈内元素，按尾部追加和删除实现后进先出；available 是存放候选下标的小根堆。它允许有重复项，也允许保留已经满了或被裁掉的过期下标，但必须保证每个现存未满栈至少有一个下标在堆中。

push 先调用 cleanAvailable：若堆顶下标越界，或对应栈已满，就弹掉它，直到堆空或堆顶有效。所有未满栈都在候选中，因此有效堆顶必定是最左未满栈；更大的过期项暂不影响选择，无需立即清理。插入后若该栈仍未满，就保留堆顶供下次使用；刚好填满时弹掉一个堆顶，残留的重复项交给以后操作的有效性检查处理。

清理后堆为空，说明现存栈都已满，可以在末尾新建一个栈。新栈若仍有容量，就把下标入堆；capacity == 1 时插入一个元素已满，无需登记。每次成功弹出也都会把下标入堆，因此创建、插入和弹出都维持了“未满栈一定有候选”的条件。

pop 先用 removeEmptyTail 连续裁掉尾部空栈，最后一个栈若存在就必定是最右非空栈。弹出后登记新空位，再清理可能新出现的空尾部。popAtStack 先检查下标和非空条件，成功弹出后登记空位；它可以暂时留下空尾栈，后续 push 能填回，pop 也会在使用前清理。

只能裁掉末尾的空栈，删除中间空栈会让后续栈编号变化。尾部编号以后可以复用，旧堆项也不必区分是哪次创建的：只要这个编号现在存在且未满，就仍是合法插入位置；否则在成为堆顶时丢弃。堆项仅表示需要检查的候选下标，并不表示一个独立空位，所以重复项不会让栈超过容量。

解题步骤

  • push 清理候选后填最左空位，或末尾新建。
  • pop 清空尾部后取最后栈。
  • 指定弹出先检查有效性，成功后登记空位。

代码实现

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);
    }
}

import "container/heap"

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
}

复杂度分析

  • 时间复杂度：$q$ 次操作总计 $O(q\log(q+1))$，均摊每次 $O(\log(q+1))$。每次操作至多新增一个堆项，每个堆项至多被弹出一次；每个新建的栈也至多被裁掉一次，所以清理循环的总次数受操作数限制。单次操作可能集中清理很多旧项，不能保证最坏时间也是对数级。
  • 空间复杂度：$O(q)$，包含保存的数据，以及可能重复或过期的堆下标；堆大小不能只按当前栈数估算。

关键点总结

[!green]

  • 堆项数量可能随操作数增长，不能只用当前栈数估算堆成本。
  • 只裁末尾空栈，保留中间下标。

易错点总结

[!yellow]

  • 清理堆顶不先检查下标范围，会访问已经裁掉的栈。
  • 成功弹出不登记下标，会漏掉可重新填补的空位。
  • 按最后栈直接弹而不跳过空尾部，会错过更左的有效数据。
  • 弹出失败时直接返回 -1，不要登记不存在的新空位；空结构上的连续弹出也都应返回 -1。

相似题目

题目 难度 关联与区别
面试题 03.03. 堆盘子 中等 同样用多个定容栈保存数据，本题push必须优先填最左未满栈，因此还需维护可用栈索引。
716. 最大栈 困难 同样在栈语义之外维护另一种选择顺序，本题按栈索引选择空位或栈顶，原题按元素极值选择。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/73576461
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！