{"id":5490,"date":"2019-08-24T22:59:35","date_gmt":"2019-08-25T05:59:35","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5490"},"modified":"2019-08-28T02:25:04","modified_gmt":"2019-08-28T09:25:04","slug":"leetcode-1172-dinner-plate-stacks","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-1172-dinner-plate-stacks\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1172. Dinner Plate Stacks"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1172. Dinner Plate Stacks - \u5237\u9898\u627e\u5de5\u4f5c EP266\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/DUsOp0HMQQg?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>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&nbsp;maximum&nbsp;<code>capacity<\/code>.<\/p>\n\n\n\n<p>Implement the&nbsp;<code>DinnerPlates<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>DinnerPlates(int capacity)<\/code>&nbsp;Initializes the object with the maximum&nbsp;<code>capacity<\/code>&nbsp;of the stacks.<\/li><li><code>void push(int val)<\/code>&nbsp;pushes the given positive integer&nbsp;<code>val<\/code>&nbsp;into the leftmost stack with size less than&nbsp;<code>capacity<\/code>.<\/li><li><code>int pop()<\/code>&nbsp;returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns&nbsp;<code>-1<\/code>&nbsp;if all stacks are empty.<\/li><li><code>int popAtStack(int index)<\/code>&nbsp;returns the value at the top of the stack with the given&nbsp;<code>index<\/code>&nbsp;and removes it from that stack, and returns -1 if the stack with that&nbsp;given&nbsp;<code>index<\/code>&nbsp;is empty.<\/li><\/ul>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input: <\/strong>\n[\"DinnerPlates\",\"push\",\"push\",\"push\",\"push\",\"push\",\"popAtStack\",\"push\",\"push\",\"popAtStack\",\"popAtStack\",\"pop\",\"pop\",\"pop\",\"pop\",\"pop\"]\n[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]\n<strong>Output: <\/strong>\n<\/pre>\n\n\n<p>[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]<\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">\n<p><strong>Explanation: <\/strong>\nDinnerPlates D = DinnerPlates(2);  \/\/ Initialize with capacity = 2\nD.push(1);\nD.push(2);\nD.push(3);\nD.push(4);\nD.push(5);         \/\/ The stacks are now:  2 &nbsp;4\n&nbsp;                                          1 &nbsp;3 &nbsp;5\n                                           \ufe48 \ufe48 \ufe48\nD.popAtStack(0);   \/\/ Returns 2.  The stacks are now:    &nbsp;4\n            &nbsp;                                          1 &nbsp;3 &nbsp;5\n                                                       \ufe48 \ufe48 \ufe48\nD.push(20);        \/\/ The stacks are now: 20  4\n&nbsp;                                          1 &nbsp;3 &nbsp;5\n                                           \ufe48 \ufe48 \ufe48\nD.push(21);        \/\/ The stacks are now: 20  4 21\n&nbsp;                                          1 &nbsp;3 &nbsp;5\n                                           \ufe48 \ufe48 \ufe48\nD.popAtStack(0);   \/\/ Returns 20.  The stacks are now:     4 21\n             &nbsp;                                          1 &nbsp;3 &nbsp;5\n                                                        \ufe48 \ufe48 \ufe48\nD.popAtStack(2);   \/\/ Returns 21.  The stacks are now:     4\n             &nbsp;                                          1 &nbsp;3 &nbsp;5\n                                                        \ufe48 \ufe48 \ufe48 \nD.pop()            \/\/ Returns 5.  The stacks are now:      4\n             &nbsp;                                          1 &nbsp;3 \n                                                        \ufe48 \ufe48  \nD.pop()            \/\/ Returns 4.  The stacks are now:   1 &nbsp;3 \n                                                        \ufe48 \ufe48   \nD.pop()            \/\/ Returns 3.  The stacks are now:   1 \n                                                        \ufe48   \nD.pop()            \/\/ Returns 1.  There are no stacks.\nD.pop()            \/\/ Returns -1.  There are still no stacks.\n<\/p>\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= capacity&nbsp;&lt;= 20000<\/code><\/li><li><code>1 &lt;= val&nbsp;&lt;= 20000<\/code><\/li><li><code>0 &lt;= index&nbsp;&lt;= 100000<\/code><\/li><li>At most&nbsp;<code>200000<\/code>&nbsp;calls will be made to&nbsp;<code>push<\/code>,&nbsp;<code>pop<\/code>, and&nbsp;<code>popAtStack<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Array of stacks + TreeSet<\/strong><\/h2>\n\n\n\n<p>Store all the stacks in an array, and store the indices of all free stacks in a tree set.<br>1. push(): find the first free stack and push onto it, if it becomes full, remove it from free set.<br>2. pop(): pop element from the last stack by calling popAtIndex(stacks.size()-1).<br>3. popAtIndex(): pop element from given index<br>  3.1 add it to free set if it was full <br>  3.2 remove it from free set if it becomes empty <br>     3.2.1 remove it from stack array if it is the last stack<\/p>\n\n\n\n<p>Time complexity:  <br>Push: O(logn)<br>Pop: O(logn)<br>PopAtIndex: O(logn)<\/p>\n\n\n\n<p>Space complexity:  O(n) <\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass DinnerPlates {\npublic:\n  DinnerPlates(int capacity): cap_(capacity) {}\n\n  void push(int val) {  \n    int index = aval_.empty() ? stacks_.size() : *begin(aval_);\n    if (index == stacks_.size()) stacks_.emplace_back();\n    stack<int>& s = stacks_[index];\n    s.push(val);\n    if (s.size() == cap_)\n      aval_.erase(index);\n    else if (s.size() == 1) \/\/ only insert for the first element\n      aval_.insert(index);\n  }\n\n  int pop() { return popAtStack(stacks_.size() - 1); }\n\n  int popAtStack(int index) {\n    if (index < 0 || index >= stacks_.size() || stacks_[index].empty()) return -1;\n    stack<int>& s = stacks_[index];\n    int val = s.top(); s.pop();\n    if (s.size() == cap_ - 1) aval_.insert(index);    \n    \n    \/\/ Amortized O(1)\n    auto it = prev(end(aval_));\n    while (stacks_.size() && stacks_.back().empty()) {\n      stacks_.pop_back();\n      aval_.erase(it--);\n    }\n    return val;\n  }\nprivate:\n  int cap_;\n  set<int> aval_;\n  vector<stack<int>> stacks_;\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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&nbsp;maximum&nbsp;capacity.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[407],"tags":[291,217,180],"class_list":["post-5490","post","type-post","status-publish","format-standard","hentry","category-stack","tag-data-structure","tag-hard","tag-stack","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5490","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5490"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5490\/revisions"}],"predecessor-version":[{"id":5503,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5490\/revisions\/5503"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5490"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5490"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5490"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}