Design a max stack that supports push, pop, top, peekMax and popMax.
- push(x) -- Push element x onto stack.
- pop() -- Remove the element on top of the stack and return it.
- top() -- Get the element on the top.
- peekMax() -- Retrieve the maximum element in the stack.
- 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:
- -1e7 <= x <= 1e7
- Number of operations won't exceed 10000.
- The last four operations won't be called when stack is empty.
Solution #1
priority queue搞不定,只能treemap。 O(logN)
class MaxStack { class Node { public Node next; public Node pre; public int val; public Node(int val) { this.val = val; next = null; pre = null; } } class DoublyLinkedList { private Node head; private Node tail; public DoublyLinkedList() { head = new Node(0); tail = new Node(0); head.next = tail; tail.pre = head; } public void addToEnd(Node node) { node.pre = tail.pre; node.pre.next = node; node.next = tail; tail.pre = node; } public void remove(Node node) { node.pre.next = node.next; node.next.pre = node.pre; } public int getLast() { return tail.pre.val; } public int removeLast() { int tmp = getLast(); remove(tail.pre); return tmp; } } private DoublyLinkedList dll; private TreeMap<Integer, LinkedList<Node>> map; /** initialize your data structure here. */ public MaxStack() { dll = new DoublyLinkedList(); map = new TreeMap<>(); } public void push(int x) { Node node = new Node(x); if (!map.containsKey(x)) { map.put(x, new LinkedList<Node>()); } map.get(x).add(node); dll.addToEnd(node); } public int pop() { int last = dll.removeLast(); map.get(last).pollLast(); if (map.get(last).isEmpty()) { map.remove(last); } return last; } public int top() { return dll.getLast(); } public int peekMax() { return map.lastKey(); } public int popMax() { int max = map.lastKey(); dll.remove(map.get(max).pollLast()); if (map.get(max).isEmpty()) { map.remove(max); } 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(); */Solution #2, 2个stack,ref:https://leetcode.com/problems/max-stack/solution/
No comments:
Post a Comment