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)

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%

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 withpopoperations, and also it's easy to compute: it's just the maximum of the element we are adding and the previous maximum.

ForpopMax, 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 popMaxoperation, 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.

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 uspopMaxquickly. We turn our attention to tree and linked-list structures that have a lower time complexity for removal, with the aim of makingpopMaxfaster 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 listdll, and store amapfromvalueto aListofNode.

• When weMaxStack.push(x), we add a node to ourdll, and add or update our entrymap.get(x).add(node).

• When weMaxStack.pop(), we find the valueval = dll.pop(), and remove the node from ourmap, deleting the entry if it was the last one.

• When weMaxStack.popMax(), we use themapto find the relevant node tounlink, and return it's value.

The above operations are more clear given that we have a workingDoubleLinkedListclass. The implementation provided usesheadandtail_sentinels_to simplify the relevantDoubleLinkedListoperations.

A Python implementation was not included for this approach because there is no analog to_TreeMap_available.

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 exceptpeekwhich is O(1), where N is the number of operations performed. Most operations involvingTreeMapare O(logN).

• Space Complexity: O(N), the size of the data structures used.

Reference

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