【一道难题】

Hello.

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

实现一个叫「餐盘」的类 DinnerPlates：

DinnerPlates(int capacity) - 给出栈的最大容量 capacity。

void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。

int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。

int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。


  示例：

1. 输入：
   
2. ["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
   
3. [[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
   
4. 输出：
   
5. [null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]
   
6. 
   
7. 解释：
   
8. DinnerPlates D = DinnerPlates(2);  // 初始化，栈最大容量 capacity = 2
   
9. D.push(1);
   
10. D.push(2);
    
11. D.push(3);
    
12. D.push(4);
    
13. D.push(5);         // 栈的现状为：    2  4
    
14.                                     1  3  5
    
15.                                     ﹈ ﹈ ﹈
    
16. D.popAtStack(0);   // 返回 2。栈的现状为：      4
    
17.                                           1  3  5
    
18.                                           ﹈ ﹈ ﹈
    
19. D.push(20);        // 栈的现状为：  20  4
    
20.                                    1  3  5
    
21.                                    ﹈ ﹈ ﹈
    
22. D.push(21);        // 栈的现状为：  20  4 21
    
23.                                    1  3  5
    
24.                                    ﹈ ﹈ ﹈
    
25. D.popAtStack(0);   // 返回 20。栈的现状为：       4 21
    
26.                                             1  3  5
    
27.                                             ﹈ ﹈ ﹈
    
28. D.popAtStack(2);   // 返回 21。栈的现状为：       4
    
29.                                             1  3  5
    
30.                                             ﹈ ﹈ ﹈
    
31. D.pop()            // 返回 5。栈的现状为：        4
    
32.                                             1  3
    
33.                                             ﹈ ﹈  
    
34. D.pop()            // 返回 4。栈的现状为：    1  3
    
35.                                            ﹈ ﹈   
    
36. D.pop()            // 返回 3。栈的现状为：    1
    
37.                                            ﹈   
    
38. D.pop()            // 返回 1。现在没有栈。
    
39. D.pop()            // 返回 -1。仍然没有栈。

复制代码

  提示：

1. 1 <= capacity <= 20000
   
2. 1 <= val <= 20000
   
3. 0 <= index <= 100000
   
4. 最多会对 push，pop，和 popAtStack 进行 200000 次调用

复制代码

卡了两小时，希望大牛点拨一下！

Hello.

&#65096;好吧这个东东打不出来

赚小钱

不会写python，可以提供一下我的思路。
需要编写两个类 `class Stack` 与 `class DinnerPlates`

1. class Stack {
   
2.     int pop();
   
3.     void push();
   
4.     bool is_full();
   
5.     bool is_empty();
   
6. }

复制代码

1. class DinnerPlates {
   
2.     map<int, Stack> buckets; // 虽然有无限个栈，但是在代码中，不能真有无限个，内存受不了，因此 key: >=0 stack 的编号， value: stack
   
3.     int capacity,
   
4. }
   

复制代码

永恒的蓝色梦想

力扣上不是有题解吗……可以参考一下的

java2python

确实，网上检索“LeetCode-Python-1172”

赚小钱

赚小钱 发表于 2020-6-18 22:20
不会写python，可以提供一下我的思路。
需要编写两个类 `class Stack` 与 `class DinnerPlates`

自己做了一下，原来还有时间要求。
我在 DinnerPlates  的数据结构中，添加了两个 Heap，元素为 stack 的 index。
一个在 Push 时使用，保存所有不满的stack的index，一个在 Pop 时使用，保存所有非空的stack 的index。
因为Push要求从左到右的顺序，所以，是一个最小堆。
Pop 要求从右到左的顺序，所以，是一个最大堆。

java2python

你可能用的是C，怎么语句后面都是分号：
用python写了个，没有用python的heapq

1. #DinnerPlates(int capacity) - 给出栈的最大容量 capacity。
   
2. #void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。
   
3. #int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。
   
4. #int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。
   
5. 
   
6. class DP:
   
7.     stacks = []
   
8.     stacks_index = []
   
9.     capacity = 5
   
10. 
    
11.     @staticmethod
    
12.     def DinnerPlates(capacity):
    
13.         DP.capacity = capacity
    
14. 
    
15.     @staticmethod
    
16.     def free_pos(start=None, end =None):
    
17.         if start == None:
    
18.             start,end = 0,len(DP.stacks)
    
19.         selected = DP.stacks_index[start:end]
    
20.         return (end-start)* DP.capacity - sum(DP.stacks_index)
    
21.         
    
22.     @staticmethod
    
23.     def first_free(start,end):
    
24.         if start == end-1:
    
25.             if DP.stacks_index[start] < DP.capacity:
    
26.                 return start
    
27.             else:
    
28.                 return -1
    
29. 
    
30.         middle = (start + end)//2
    
31.         part1 = DP.first_free(start,middle)
    
32.         return part1 if part1 !=-1 else DP.first_free(middle,end)
    
33. 
    
34.     @staticmethod
    
35.     def first_filled(start,end):
    
36.         if start == end-1:
    
37.             if DP.stacks_index[start] > 0:
    
38.                 return start
    
39.             else:
    
40.                 return -1
    
41. 
    
42.         middle = (start + end)//2
    
43.         part1 = DP.first_filled(middle,end)
    
44.         return part1 if part1 !=-1 else DP.first_filled(start,middle)
    
45. 
    
46.     @staticmethod
    
47.     def push(val):
    
48.         if DP.free_pos()>0:
    
49.             index = DP.first_free(0,len(DP.stacks))
    
50.         else:
    
51.             index = len(DP.stacks)
    
52.             stack = [-1 for i in range(DP.capacity)]
    
53.             DP.stacks.append(stack)
    
54.             DP.stacks_index.append(0)
    
55.         DP.stacks[index][DP.stacks_index[index]] = val
    
56.         DP.stacks_index[index] += 1
    
57.     @staticmethod
    
58.     def pop():
    
59.         if sum(DP.stacks_index) == 0:
    
60.             return -1
    
61.         else:
    
62.             index = DP.first_filled(0,len(DP.stacks))
    
63.             DP.stacks_index[index] -= 1
    
64.             return DP.stacks[index][DP.stacks_index[index]]
    
65.     @staticmethod
    
66.     def popAtStack(index):
    
67.         if index < len(DP.stacks) and DP.stacks_index[index] > 0:
    
68.             DP.stacks_index[index] -= 1
    
69.             return DP.stacks[index][DP.stacks_index[index]]
    
70.         else:
    
71.             return -1
    
72.        
    
73. DP.DinnerPlates(2)
    
74. DP.push(1)
    
75. DP.push(2)
    
76. DP.push(3)
    
77. DP.push(4)
    
78. DP.push(5)
    
79. print(DP.stacks,DP.stacks_index,DP.capacity)
    
80. DP.popAtStack(0)
    
81. print(DP.stacks,DP.stacks_index,DP.capacity)
    
82. DP.push(20)
    
83. print(DP.stacks,DP.stacks_index,DP.capacity)
    
84. print(DP.stacks,DP.stacks_index,DP.capacity)
    
85. DP.popAtStack(0)
    
86. print(DP.stacks,DP.stacks_index,DP.capacity)
    
87. DP.push(20)
    
88. print(DP.stacks,DP.stacks_index,DP.capacity)
    
89. DP.push(21)
    
90. print(DP.stacks,DP.stacks_index,DP.capacity)
    
91. DP.popAtStack(0)
    
92. print(DP.stacks,DP.stacks_index,DP.capacity)
    
93. DP.popAtStack(2)
    
94. print(DP.stacks,DP.stacks_index,DP.capacity)
    
95. DP.pop()
    
96. print(DP.stacks,DP.stacks_index,DP.capacity)
    
97. DP.pop()
    
98. print(DP.stacks,DP.stacks_index,DP.capacity)
    
99. DP.pop()
    
100. print(DP.stacks,DP.stacks_index,DP.capacity)
     
101. DP.pop()
     
102. print(DP.stacks,DP.stacks_index,DP.capacity)
     
103. DP.pop()
     
104. print(DP.stacks,DP.stacks_index,DP.capacity)

复制代码

结果（栈列表，以及各栈的栈顶指针，指针为零，栈内值不设置为-1的，主要看栈顶指针）：
栈列表，栈顶指针，最后一个2是容量（这个可以无视）
[[1, 2], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 2], [3, 4], [5, -1]] [1, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [1, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 20], [3, 4], [5, 21]] [2, 2, 2] 2
[[1, 20], [3, 4], [5, 21]] [1, 2, 2] 2
[[1, 20], [3, 4], [5, 21]] [1, 2, 1] 2
[[1, 20], [3, 4], [5, 21]] [1, 2, 0] 2
[[1, 20], [3, 4], [5, 21]] [1, 1, 0] 2
[[1, 20], [3, 4], [5, 21]] [1, 0, 0] 2
[[1, 20], [3, 4], [5, 21]] [0, 0, 0] 2
[[1, 20], [3, 4], [5, 21]] [0, 0, 0] 2

lijiachen

java2python 发表于 2020-6-19 19:32
你可能用的是C，怎么语句后面都是分号：
用python写了个，没有用python的heapq