餐盘栈【LC1172】
我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。
实现一个叫「餐盘」的类 DinnerPlates：
DinnerPlates(int capacity)- 给出栈的最大容量capacity。void push(int val)- 将给出的正整数val推入 从左往右第一个 没有满的栈。int pop()- 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回-1。int popAtStack(int index)- 返回编号index的栈顶部的值，并将其从栈中删除；如果编号index的栈是空的，请返回-1。
思路
暴力超时，学习灵神的做法
- 为了快速查找从左到右未存满的第一个栈，使用小顶堆存储未满元素的下标
- 并使用动态数组记录每一个栈
push方法分为两种情况：- 有未满栈：弹出堆顶元素，在对应的栈中添加元素
- 无未满栈：添加一个新栈，在其中添加元素
- 添加元素后，需要判断当前栈是否已满，如果已满，那么从小顶堆中弹出
pop方法：将最后一个栈中的元素弹出，即调用popAtStack(stacks.size()-1)popAtStack(index)
- 如果不存在该栈，即目前没有元素可以弹出，那么返回-1
- 如果该栈为满栈，那么弹出元素后即为未满栈，将其放入小顶堆中
- 使用懒删除：不同步删除小顶堆的下标，如果在
push时发现堆顶的下标大于等于stacks的长度，把整个堆清空即可。 - 实现
class DinnerPlates { // 栈的容量 private int capacity; // 所有栈 private List<Deque<Integer>> stacks = new ArrayList<>(); // 最小堆，保存未满栈的下标 private PriorityQueue<Integer> idx = new PriorityQueue<>(); public DinnerPlates(int capacity) { this.capacity = capacity; } public void push(int val) { if (!idx.isEmpty() && idx.peek() >= stacks.size()) idx.clear(); // 堆中都是越界下标，直接清空 if (idx.isEmpty()) { // 所有栈都是满的 var st = new ArrayDeque<Integer>(); st.push(val); stacks.add(st); // 添加一个新的栈 if (capacity > 1) // 新的栈没有满 idx.add(stacks.size() - 1); // 入堆 } else { // 还有未满栈 var st = stacks.get(idx.peek()); st.push(val); // 入栈 if (st.size() == capacity) // 栈满了 idx.poll(); // 从堆中去掉 } } public int pop() { // 等价为 popAtStack 最后一个非空栈 return popAtStack(stacks.size() - 1); } public int popAtStack(int index) { if (index < 0 || index >= stacks.size() || stacks.get(index).isEmpty()) return -1; // 非法操作 var st = stacks.get(index); if (st.size() == capacity) // 满栈 idx.add(index); // 元素出栈后，栈就不满了，把下标入堆 int val = st.pop(); // 去掉末尾的空栈（懒删除，堆中下标在 push 时处理） while (!stacks.isEmpty() && stacks.get(stacks.size() - 1).isEmpty()) stacks.remove(stacks.size() - 1); return val; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/dinner-plate-stacks/solutions/2248707/yu-qi-wei-hu-di-yi-ge-wei-man-zhan-bu-ru-sphs/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(qlogq)，q为操作次数
- 空间复杂度：O(q)
————————————————
版权声明：本文为CSDN博主「TIkitianya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Tikitian/article/details/130432288
