#278 Queue With Running Maximum

An upload manager keeps pending file sizes in a first-in-first-out queue and shows the largest pending size. Write a class MaxQueue:

• enqueue(size) adds a size at the back.
• dequeue() removes and returns the oldest size, or -1 if the queue is empty.
• max() returns the largest size in the queue, or -1 if it is empty.

Each call should take O(1) time on average.

Each example lists the calls in order, then each call's arguments. The first call creates the object with new MaxQueue(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Input: ["MaxQueue","enqueue","enqueue","enqueue","max","dequeue","max","dequeue","max"]
[[],[3],[9],[4],[],[],[],[],[]]
Output: [null,null,null,null,9,3,9,9,4]

Input: ["MaxQueue","max","dequeue"]
[[],[],[]]
Output: [null,-1,-1]

Constraints

• 1 <= size <= 10^5
• At most 10^4 calls.