1172：餐盘栈（2109 分）

2019-08-25 约 812 字预计阅读 2 分钟次阅读

力扣第 151 场周赛第 4 题

题目

我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。

实现一个叫「餐盘」的类 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 <= 20000
1 <= val <= 20000
0 <= index <= 100000
最多会对 push，pop，和 popAtStack 进行 200000 次调用。

分析

#1 有序集合

最简单的就是维护两个有序集合
- nfull 维护没有满的栈
- nvoid 维护非空的栈
push 和 pop 时更新两个有序集合即可
由于 nfull 只有添加和删除最值的操作，可以用堆

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class DinnerPlates:

    def __init__(self, capacity: int):
        from sortedcontainers import SortedList
        self.ca = capacity
        self.A = []
        self.nfull = []
        self.nvoid = SortedList()

    def push(self, val: int) -> None:
        if self.nfull:
            i = heappop(self.nfull)
        else:
            i = len(self.A)
            self.A.append([])
        self.A[i].append(val)
        if len(self.A[i])<self.ca:
            heappush(self.nfull,i)
        if len(self.A[i])==1:
            self.nvoid.add(i)

    def pop(self) -> int:
        if not self.nvoid:
            return -1
        return self.popAtStack(self.nvoid[-1])

    def popAtStack(self, index: int) -> int:
        if not (0<=index<len(self.A) and self.A[index]):
            return -1
        x = self.A[index].pop()
        if len(self.A[index])==self.ca-1:
            heappush(self.nfull,index)
        if not self.A[index]:
            self.nvoid.remove(index)
        return x

480 ms

#2 堆

还可以注意维护数组 A，保证末尾非空，那么无需维护 nvoid
此时 nfull 采用懒删除即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class DinnerPlates:

    def __init__(self, capacity: int):
        self.ma = capacity
        self.A = []
        self.nfull = []

    def push(self, val: int) -> None:
        nfull,A = self.nfull,self.A
        if not nfull or nfull[0]>=len(A):
            nfull.clear()
            i = len(A)
            A.append([])
        else:
            i = heappop(nfull)
        A[i].append(val)
        if len(A[i])<self.ma:
            heappush(nfull, i)

    def pop(self) -> int:
        return self.popAtStack(len(self.A)-1)

    def popAtStack(self, index: int) -> int:
        nfull,A = self.nfull,self.A
        if not (0<=index<len(A) and A[index]):
            return -1
        x = A[index].pop()
        if len(A[index])==self.ma-1:
            heappush(nfull,index)
        while A and not A[-1]:
            A.pop()
        return x

176 ms

目录

1172：餐盘栈（2109 分）

题目

分析

#1 有序集合

#2 堆

解答