716. Max Stack

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Design a max stack data structure that supports the stack operations and supports finding the stack’s maximum element.

Implement the MaxStack class:

MaxStack() Initializes the stack object. void push(int x) Pushes element x onto the stack. int pop() Removes the element on top of the stack and returns it. int top() Gets the element on the top of the stack without removing it. int peekMax() Retrieves the maximum element in the stack without removing it. int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

Code

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

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

    public void push(int x) {
        int max = Integer.MIN_VALUE;
        if (!maxStack.isEmpty()) {
            max = maxStack.peek();
        }

        if (max > x) {
            maxStack.push(max);
        } else {
            maxStack.push(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> temp = new Stack();
        while (top() != max) temp.push(pop());
        pop();
        while (!temp.isEmpty()) push(temp.pop());
        return max;
    }
}

最优解

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<>());
        }
        // 有可能同一个值多次加入
        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();
        // 得到这个值的所有node
        List<Node> list = map.get(max);
        // 删除最后加入的
        Node node = list.remove(list.size() - 1);
        dll.remove(node);
        if (list.isEmpty()) {
            map.remove(max);
        }
        return max;
    }
}

class DoubleLinkedList {
    Node head;
    Node tail;

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

    public Node add(int val) {
        Node node = new Node(val);
        // 把node插入到tail和前一个点之间
        // 这样node就是真实的tail
        node.next = tail;
        // 连接node和之前的真实的tail
        node.prev = tail.prev;
        // 之前的真实的tail
        tail.prev.next = node;
        tail.prev = node;
        return node;
    }

    public int pop() {
        // 去掉当前真实的tail
        return remove(tail.prev).val;
    }

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

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

class Node {
    int val;
    Node prev;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}

time: O(logN) space: O(N)