[LintCode] Problem 859 - Max Stack

Posted on | In ,

Design a max stack that supports push, pop, top, peekMax and popMax.

  1. push(x) – Push element x onto stack.
  2. pop() – Remove the element on top of the stack and return it.
  3. top() – Get the element on the top.
  4. peekMax() – Retrieve the maximum element in the stack.
  5. popMax() – Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Note

  1. -1e7 <= x <= 1e7
  2. Number of operations won’t exceed 10000.
  3. The last four operations won’t be called when stack is empty.

Example

Input:
push(5)
push(1)
push(5)
top()
popMax()
top()
peekMax()
pop()
top()

Output:
5
5
1
5
1
5

Code

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
38
39
40
41
42
43
44
45
46
47
48
class MaxStack {
    private Stack<Integer> stack;
    private Stack<Integer> max;

    public MaxStack() {
        stack = new Stack<>();
        max = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);

        if (max.isEmpty() || max.peek() <= x)
            max.push(x);
    }

    public int pop() {
        int x = stack.pop();

        if (max.peek() == x)
            max.pop();
        
        return x;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return max.peek();
    }

    public int popMax() {
        int x = max.pop();
        Stack<Integer> temp = new Stack<>();

        while (stack.peek() != x)
            temp.push(stack.pop());
        
        stack.pop();

        while (!temp.isEmpty())
            stack.push(temp.pop());

        return x;
    }
}