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 maximumcapacity
of the stacks.void push(int val)
pushes the given positive integerval
into the leftmost stack with size less thancapacity
.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 givenindex
and removes it from that stack, and returns -1 if the stack with that givenindex
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 topush
,pop
, andpopAtStack
.
Solution: Array of stacks + TreeSet
Store all the stacks in an array, and store the indices of all free stacks in a tree set.
1. push(): find the first free stack and push onto it, if it becomes full, remove it from free set.
2. pop(): pop element from the last stack by calling popAtIndex(stacks.size()-1).
3. popAtIndex(): pop element from given index
3.1 add it to free set if it was full
3.2 remove it from free set if it becomes empty
3.2.1 remove it from stack array if it is the last stack
Time complexity:
Push: O(logn)
Pop: O(logn)
PopAtIndex: O(logn)
Space complexity: O(n)
C++
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 36 37 |
// Author: Huahua class DinnerPlates { public: DinnerPlates(int capacity): cap_(capacity) {} void push(int val) { int index = aval_.empty() ? stacks_.size() : *begin(aval_); if (index == stacks_.size()) stacks_.emplace_back(); stack<int>& s = stacks_[index]; s.push(val); if (s.size() == cap_) aval_.erase(index); else if (s.size() == 1) // only insert for the first element aval_.insert(index); } int pop() { return popAtStack(stacks_.size() - 1); } int popAtStack(int index) { if (index < 0 || index >= stacks_.size() || stacks_[index].empty()) return -1; stack<int>& s = stacks_[index]; int val = s.top(); s.pop(); if (s.size() == cap_ - 1) aval_.insert(index); // Amortized O(1) auto it = prev(end(aval_)); while (stacks_.size() && stacks_.back().empty()) { stacks_.pop_back(); aval_.erase(it--); } return val; } private: int cap_; set<int> aval_; vector<stack<int>> stacks_; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment