Hard

题目描述

你有无数个栈，排成一行，按从左到右的顺序从 0 开始编号，每个栈的都有相同的最大容量。

实现一个叫DinnerPlates的类：

  • DinnerPlates(int capacity) 给一个栈的最大容量 capacity。
  • void push(int val) 将给出的正整数 val 推入 从左往右第一个 没有满的栈。
  • int pop() 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。
  • int popAtStack(int index) 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。

示例：

输入: 
["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"]
[[2], [1], [2], [3], [4], [5], [0], [20], [21], [0], [2], [], [], [], [], []]
输出:
[null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]

解释：
DinnerPlates D = DinnerPlates(2);  // 初始化，容量 capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // 栈的现状为:  2  4
                                 1  3  5
                                 ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 2。现在栈的现状为:     4
                                            1  3  5
                                            ﹈ ﹈ ﹈
D.push(20);        // 栈的现状为: 20  4
                                 1  3  5
                                 ﹈ ﹈ ﹈
D.push(21);        // 栈的现状为: 20  4 21
                                 1  3  5
                                 ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 20。现在栈的现状为:     4 21
                                              1  3  5
                                              ﹈ ﹈ ﹈
D.popAtStack(2);   // 返回 21。现在栈的现状为:     4
                                              1  3  5
                                              ﹈ ﹈ ﹈ 
D.pop()            // 返回 5。现在栈的现状为:      4
                                              1  3 
                                              ﹈ ﹈  
D.pop()            // 返回 4。现在栈的现状为:   1  3 
                                              ﹈ ﹈   
D.pop()            // 返回 3。现在栈的现状为:   1 
                                              ﹈   
D.pop()            // 返回 1。现在没有栈。
D.pop()            // 返回 -1。仍然没有栈。

提示：

  • 1 <= capacity <= 2 * 10^4
  • 1 <= val <= 2 * 10^4
  • 0 <= index <= 10^5
  • 最多会对 push、pop 和 popAtStack 进行 2 * 10^5 次调用。

解题思路

这道题目需要我们实现一个栈的集合，关键在于高效地维护可用位置和最右端的非空栈。

核心思路：

  1. 使用栈数组存储所有的栈
  2. 使用最小堆维护所有未满栈的索引，保证 push 时能快速找到最左边的可用栈
  3. 维护一个变量记录最右边的非空栈位置，保证 pop 时能快速找到

具体实现：

  • push操作：从最小堆中取出最小的未满栈索引，插入元素。如果堆为空，则创建新栈
  • pop操作：从右向左遍历找到第一个非空栈，弹出元素
  • popAtStack操作：直接在指定位置弹出，如果该栈变为未满状态，将其索引加入堆中

优化细节：

  • 使用堆来维护未满栈的索引，确保总是选择最左边的可用栈
  • 及时清理堆中已满栈的索引，避免无效操作
  • 动态调整最右边非空栈的位置，提高 pop 操作效率

这种方法在大部分操作上都能达到较好的时间复杂度，特别适合题目给定的约束条件。

代码实现

class DinnerPlates {
private:
    int capacity;
    vector<stack<int>> stacks;
    priority_queue<int, vector<int>, greater<int>> available; // 最小堆，存储未满栈的索引
    
public:
    DinnerPlates(int capacity) : capacity(capacity) {
    }
    
    void push(int val) {
        // 清理已满的栈索引
        while (!available.empty() && stacks[available.top()].size() == capacity) {
            available.pop();
        }
        
        if (available.empty()) {
            // 需要新的栈
            stacks.push_back(stack<int>());
            available.push(stacks.size() - 1);
        }
        
        int idx = available.top();
        stacks[idx].push(val);
        
        // 如果栈满了，从堆中移除
        if (stacks[idx].size() == capacity) {
            available.pop();
        }
    }
    
    int pop() {
        // 从右向左找第一个非空栈
        while (!stacks.empty() && stacks.back().empty()) {
            stacks.pop_back();
        }
        
        if (stacks.empty()) {
            return -1;
        }
        
        int val = stacks.back().top();
        stacks.back().pop();
        
        // 如果栈变成未满状态，加入可用堆
        if (stacks.back().size() == capacity - 1) {
            available.push(stacks.size() - 1);
        }
        
        return val;
    }
    
    int popAtStack(int index) {
        if (index >= stacks.size() || stacks[index].empty()) {
            return -1;
        }
        
        int val = stacks[index].top();
        stacks[index].pop();
        
        // 如果栈变成未满状态，加入可用堆
        if (stacks[index].size() == capacity - 1) {
            available.push(index);
        }
        
        return val;
    }
};

import heapq

class DinnerPlates:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks = []
        self.available = []  # 最小堆，存储未满栈的索引
    
    def push(self, val: int) -> None:
        # 清理已满的栈索引
        while self.available and len(self.stacks[self.available[0]]) == self.capacity:
            heapq.heappop(self.available)
        
        if not self.available:
            # 需要新的栈
            self.stacks.append([])
            heapq.heappush(self.available, len(self.stacks) - 1)
        
        idx = self.available[0]
        self.stacks[idx].append(val)
        
        # 如果栈满了，从堆中移除
        if len(self.stacks[idx]) == self.capacity:
            heapq.heappop(self.available)
    
    def pop(self) -> int:
        # 从右向左找第一个非空栈
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()
        
        if not self.stacks:
            return -1
        
        val = self.stacks[-1].pop()
        
        # 如果栈变成未满状态，加入可用堆
        if len(self.stacks[-1]) == self.capacity - 1:
            heapq.heappush(self.available, len(self.stacks) - 1)
        
        return val
    
    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks) or not self.stacks[index]:
            return -1
        
        val = self.stacks[index].pop()
        
        # 如果栈变成未满状态，加入可用堆
        if len(self.stacks[index]) == self.capacity - 1:
            heapq.heappush(self.available, index)
        
        return val

public class DinnerPlates {
    private int capacity;
    private List<Stack<int>> stacks;
    private PriorityQueue<int, int> available; // 最小堆，存储未满栈的索引
    
    public DinnerPlates(int capacity) {
        this.capacity = capacity;
        stacks = new List<Stack<int>>();
        available = new PriorityQueue<int, int>();
    }
    
    public void Push(int val) {
        // 清理已满的栈索引
        while (available.Count > 0 && stacks[available.Peek()].Count == capacity) {
            available.Dequeue();
        }
        
        if (available.Count == 0) {
            // 需要新的栈
            stacks.Add(new Stack<int>());
            available.Enqueue(stacks.Count - 1, stacks.Count - 1);
        }
        
        int idx = available.Peek();
        stacks[idx].Push(val);
        
        // 如果栈满了，从堆中移除
        if (stacks[idx].Count == capacity) {
            available.Dequeue();
        }
    }
    
    public int Pop() {
        // 从右向左找第一个非空栈
        while (stacks.Count > 0 && stacks[stacks.Count - 1].Count == 0) {
            stacks.RemoveAt(stacks.Count - 1);
        }
        
        if (stacks.Count == 0) {
            return -1;
        }
        
        int val = stacks[stacks.Count - 1].Pop();
        
        // 如果栈变成未满状态，加入可用堆
        if (stacks[stacks.Count - 1].Count == capacity - 1) {
            available.Enqueue(stacks.Count - 1, stacks.Count - 1);
        }
        
        return val;
    }
    
    public int PopAtStack(int index) {
        if (index >= stacks.Count || stacks[index].Count == 0) {
            return -1;
        }
        
        int val = stacks[index].Pop();
        
        // 如果栈变成未满状态，加入可用堆
        if (stacks[index].Count == capacity - 1) {
            available.Enqueue(index, index);
        }
        
        return val;
    }
}

var DinnerPlates = function(capacity) {
    this.capacity = capacity;
    this.stacks = [];
    this.availableStacks = new Set();
};

DinnerPlates.prototype.push = function(val) {
    let targetStack = -1;
    
    for (let i = 0; i < this.stacks.length; i++) {
        if (this.stacks[i].length < this.capacity) {
            targetStack = i;
            break;
        }
    }
    
    if (targetStack === -1) {
        this.stacks.push([]);
        targetStack = this.stacks.length - 1;
    }
    
    this.stacks[targetStack].push(val);
    
    if (this.stacks[targetStack].length === this.capacity) {
        this.availableStacks.delete(targetStack);
    } else {
        this.availableStacks.add(targetStack);
    }
};

DinnerPlates.prototype.pop = function() {
    while (this.stacks.length > 0 && this.stacks[this.stacks.length - 1].length === 0) {
        this.stacks.pop();
        this.availableStacks.delete(this.stacks.length);
    }
    
    if (this.stacks.length === 0) {
        return -1;
    }
    
    let lastStack = this.stacks.length - 1;
    let val = this.stacks[lastStack].pop();
    
    if (this.stacks[lastStack].length === 0) {
        this.stacks.pop();
        this.availableStacks.delete(lastStack);
    } else {
        this.availableStacks.add(lastStack);
    }
    
    return val;
};

DinnerPlates.prototype.popAtStack = function(index) {
    if (index >= this.stacks.length || this.stacks[index].length === 0) {
        return -1;
    }
    
    let val = this.stacks[index].pop();
    this.availableStacks.add(index);
    
    return val;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-