1608. Peak Stack Desk
A clerk keeps a pile of tickets, each carrying an integer priority, and always works on the newest ticket on top. Design PeakStack with these operations. push(x) puts a ticket with value x on top and returns nothing. pop() removes the top ticket and returns its value. top() returns the top value without removing it. peekMax() returns the largest value in the pile without removing it. popMax() removes the largest ticket and returns its value; when several tickets share that largest value, the one that was pushed most recently is removed, and every other ticket keeps its place. Values lie in the 32-bit range, there are at most 2000 calls, and every call except push is made on a non-empty pile. Each call should run in O(log n) time.
Example 1
- Input:
- operations = ["PeakStack","push","push","push","peekMax","popMax","top","popMax","top"]arguments = [[],[5],[1],[5],[],[],[],[],[]]
- Output:
- [null,null,null,null,5,5,1,5,1]
- Explanation:
popMax removes the later 5, leaving 5, 1 so top is 1; the next popMax returns 5 and top becomes 1.
Example 2
- Input:
- operations = ["PeakStack","push","top","pop"]arguments = [[],[3],[],[]]
- Output:
- [null,null,3,3]
- Explanation:
A single ticket is both the top and the maximum.
Constraints
-109 ≤ x ≤ 109
at most 2000 calls
pop, top, peekMax and popMax are only called on a non-empty stack
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(log n) per call
- Space
- O(n)