# 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/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/stack/max-stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.