• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1172.餐盘栈|DinnerPlateStacks

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(www.zengqiang.org
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

  • DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
  • void push(int val) pushes the given positive integer val into the leftmost stack with size less than capacity.
  • int pop() returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
  • int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index is empty.

Example:

Input: 
["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],[],[],[],[],[]]
Output: 
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

Explanation: 
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.

Constraints:

  • 1 <= capacity <= 20000
  • 1 <= val <= 20000
  • 0 <= index <= 100000
  • At most 200000 calls will be made to pushpop, and popAtStack.

我们把无限数量 ∞ 的栈排成一行,按从左到右的次序从 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
  • 最多会对 pushpop,和 popAtStack 进行 200000 次调用。

Runtime: 2024 ms
Memory Usage: 45 MB
 1 class DinnerPlates {
 2     var map:[Int:[Int]] = [Int:[Int]]()
 3     var cap:Int = 0
 4     var curr:Int = 0
 5     var last:Int = 0
 6     var count:Int = 0
 7 
 8     init(_ capacity: Int) {
 9         self.cap = capacity
10         map[curr] = [Int]()        
11     }
12     
13     func push(_ val: Int) {
14         while(map[curr] != nil  && map[curr,default:[Int]()].count == cap)
15         {
16             curr += 1
17         }
18         map[curr,default:[Int]()].append(val)
19         last = max(last, curr)
20         count += 1
21         
22     }
23     
24     func pop() -> Int {
25         if count == 0 {return -1}
26         while(last>=0 && map[last,default:[Int]()].isEmpty)
27         {
28             last -= 1
29         }
30         count -= 1
31         curr = min(curr, last)
32         return map[last,default:[Int]()].removeLast()
33     }
34     
35     func popAtStack(_ index: Int) -> Int {
36         if(map[index] == nil || map[index,default:[Int]()].isEmpty)
37         {
38             return -1
39         }
40         count -= 1
41         curr = min(curr, index)
42         return map[index,default:[Int]()].removeLast()
43     }
44 }
45 
46 /**
47  * Your DinnerPlates object will be instantiated and called as such:
48  * let obj = DinnerPlates(capacity)
49  * obj.push(val)
50  * let ret_2: Int = obj.pop()
51  * let ret_3: Int = obj.popAtStack(index)
52  */

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift - TableView 创建局部显示/自定义容器 的 TableView发布时间:2022-07-13
下一篇:
swift-入门学习教程第一讲发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap