# Max Stack

`Design`

**Easy**

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.

**Example 1:**

```
MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5
```

**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.

## Solution & Analysis

### Two Stack + Custom Class

主要思想：用Element这个custom class，存入val以及当前max。这样只需在push时比较栈顶就能得到当前max。

唯一的难点在popMax()，因为只需要pop max值对应的元素，因此需要辅助stack来存pop出来的元素，当pop 完 max 元素之后，再将辅助stack中元素push回原来的stack即可，但是这是要用MaxStack class本身的push(int x)，因为需要更新此时stack中的max。此外可以进一步优化push()，再创建一个push(Element e)，这样就可以不用每次stack.push时都new一下Element。

Time: O(n)

Space: O(n)

```java
class MaxStack {
    class Element {
        int val;
        int max;
        public Element(int val, int max) {
            this.val = val;
            this.max = max;
        }
    }

    private Deque<Element> stack;
    private Deque<Element> aux;

    /** initialize your data structure here. */
    public MaxStack() {
        stack = new ArrayDeque<Element>();
        aux = new ArrayDeque<Element>();
    }

    public void push(int x) {
        int max = x;
        if (!stack.isEmpty()) {
            max = Math.max(x, stack.peek().max);
        }

        stack.push(new Element(x, max));
    }

    public int pop() {
        if (stack.isEmpty()) {
            return -1;
        }
        return stack.pop().val;
    }

    public int top() {
        if (stack.isEmpty()) {
            return -1;
        }
        return stack.peek().val;
    }

    public int peekMax() {
        if (stack.isEmpty()) {
            return -1;
        }
        return stack.peek().max;
    }

    public int popMax() {
        if (stack.isEmpty()) {
            return -1;
        }
        int max = stack.peek().max;
        while (!stack.isEmpty() && stack.peek().val != max) {
            aux.push(stack.pop());
        }
        // pop the max
        if (!stack.isEmpty()) {
            stack.pop();
        }

        while (!aux.isEmpty()) {
            push(aux.pop().val);
        }
        return max;
    }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */
```

### Space Optimized - push(Element e) to reuse Element objects

Time: 81 ms, faster than 94.91%

Space: 40.3 MB, less than 100.00%

```java
class MaxStack {
    class Element {
        int val;
        int max;
        public Element(int val, int max) {
            this.val = val;
            this.max = max;
        }
    }

    private Deque<Element> stack;
    private Deque<Element> aux;

    /** initialize your data structure here. */
    public MaxStack() {
        stack = new ArrayDeque<Element>();
        aux = new ArrayDeque<Element>();
    }

    public void push(int x) {
        int max = x;
        if (!stack.isEmpty()) {
            max = Math.max(x, stack.peek().max);
        }

        stack.push(new Element(x, max));
    }

    private void push(Element e) {
        int max = e.val;
        if (!stack.isEmpty()) {
            max = Math.max(e.val, stack.peek().max);
        }
        e.max = max;
        stack.push(e);
    }

    public int pop() {
        return stack.pop().val;
    }

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

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

    public int popMax() {
        int max = stack.peek().max;
        while (!stack.isEmpty() && stack.peek().val != max) {
            aux.push(stack.pop());
        }
        // pop the max
        if (!stack.isEmpty()) {
            stack.pop();
        }

        while (!aux.isEmpty()) {
            push(aux.pop());
        }
        return max;
    }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */
```

### LeetCode Official - Approach #1: Two Stacks

For `peekMax`, we remember the largest value we've seen on the side. For example if we add `[2, 1, 5, 3, 9]` in stack , we'll store `[2, 2, 5, 5, 9]` in maxStack. This works seamlessly with`pop`operations, and also it's easy to compute: it's just the maximum of the element we are adding and the previous maximum.

For`popMax`, we know what the current maximum (`peekMax`) is. We can pop until we find that maximum, then push the popped elements back on the stack.

* Time Complexity: O(N) for the `popMax`operation, and O(1) for the other operations, where N is the number of operations performed.
* Space Complexity: O(N), the maximum size of the stack.

```java
class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> maxStack;

    public MaxStack() {
        stack = new Stack();
        maxStack = new Stack();
    }

    public void push(int x) {
        int max = maxStack.isEmpty() ? x : maxStack.peek();
        maxStack.push(max > x ? max : x);
        stack.push(x);
    }

    public int pop() {
        maxStack.pop();
        return stack.pop();
    }

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

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

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}
```

### LeetCode Official - Approach #2: Double Linked List + TreeMap

**Intuition**

Using structures like Array or Stack will never let us`popMax`quickly. We turn our attention to tree and linked-list structures that have a lower time complexity for removal, with the aim of making`popMax`faster than O(N) time complexity.

Say we have a double linked list as our "stack". This reduces the problem to finding which node to remove, since we can remove nodes in O(1) time.

We can use a TreeMap mapping values to a list of nodes to answer this question. TreeMap can find the largest value, insert values, and delete values, all in O(logN) time.

**Algorithm**

Let's store the stack as a double linked list`dll`, and store a`map`from`value`to a`List`of`Node`.

* When we`MaxStack.push(x)`, we add a node to our`dll`, and add or update our entry`map.get(x).add(node)`.
* When we`MaxStack.pop()`, we find the value`val = dll.pop()`, and remove the node from our`map`, deleting the entry if it was the last one.
* When we`MaxStack.popMax()`, we use the`map`to find the relevant node to`unlink`, and return it's value.

The above operations are more clear given that we have a working`DoubleLinkedList`class. The implementation provided uses`head`and`tail`\_sentinels\_to simplify the relevant`DoubleLinkedList`operations.

A Python implementation was not included for this approach because there is no analog to\_TreeMap\_available.

```java
class MaxStack {
    TreeMap<Integer, List<Node>> map;
    DoubleLinkedList dll;

    public MaxStack() {
        map = new TreeMap();
        dll = new DoubleLinkedList();
    }

    public void push(int x) {
        Node node = dll.add(x);
        if(!map.containsKey(x))
            map.put(x, new ArrayList<Node>());
        map.get(x).add(node);
    }

    public int pop() {
        int val = dll.pop();
        List<Node> L = map.get(val);
        L.remove(L.size() - 1);
        if (L.isEmpty()) map.remove(val);
        return val;
    }

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

    public int peekMax() {
        return map.lastKey();
    }

    public int popMax() {
        int max = peekMax();
        List<Node> L = map.get(max);
        Node node = L.remove(L.size() - 1);
        dll.unlink(node);
        if (L.isEmpty()) map.remove(max);
        return max;
    }
}

class DoubleLinkedList {
    Node head, tail;

    public DoubleLinkedList() {
        head = new Node(0);
        tail = new Node(0);
        head.next = tail;
        tail.prev = head;
    }

    public Node add(int val) {
        Node x = new Node(val);
        x.next = tail;
        x.prev = tail.prev;
        tail.prev = tail.prev.next = x;
        return x;
    }

    public int pop() {
        return unlink(tail.prev).val;
    }

    public int peek() {
        return tail.prev.val;
    }

    public Node unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        return node;
    }
}

class Node {
    int val;
    Node prev, next;
    public Node(int v) {val = v;}
}
```

**Complexity Analysis**

* Time Complexity: O(logN) for all operations except`peek`which is O(1), where N is the number of operations performed. Most operations involving`TreeMap`are O(logN).
* Space Complexity: O(N), the size of the data structures used.

## Reference

<https://leetcode.com/problems/max-stack/solution/>