Max Stack

犯错：popMax的时候 没有把对应的node从map里删除

时间复杂度 o(logn)

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.

这道题一般stack的地方用double linked list 维护 求max的地方，用map维护，key是值，value是node的list，因为存在可能相同的数值被加进stack里， 因为treemap可以给key排序，所有pop max的时候 直接从map最后一个取就好了

time O(logn) space o(n);

TreeMap:

• For operations like add, remove, containsKey, time complexity is O(log n where n is number of elements present in TreeMap.

• TreeMap always keeps the elements in a sorted(increasing) order, while the elements in a HashMap have no order. TreeMap also provides some cool methods for first, last, floor and ceiling of keys.

HashMap:

• Complexity: get/put/containsKey() operations are O(1) in average case but we can’t guarantee that since it all depends on how much time does it take to compute the hash.

时间复杂度 peek 是o(1),其他是o(logn)

class MaxStack {

    /** initialize your data structure here. */
    
    private DoubleLinkedList ddl;
    private TreeMap<Integer, List<Node>> map;
    public MaxStack() {
        ddl = new DoubleLinkedList();
        map = new TreeMap<>();
    }
    
    public void push(int x) {
        
        Node node = new Node(x);
        ddl.add(node);
        if(!map.containsKey(x)){
            
            List<Node> tmp = new ArrayList<>();
            tmp.add(node);
            map.put(x,tmp);
        }else{
            map.get(x).add(node);
        }
        
        
    }
    
    public int pop() {
        int val = ddl.pop();
        
        //从map中删除
        
        map.get(val).remove(map.get(val).size()-1);
        
        if(map.get(val).isEmpty())
            map.remove(val);
        
        return val;
    }
    
    public int top() {
        return ddl.peek();
    }
    
    public int peekMax() {
        return map.lastKey();
    }
    
    public int popMax() {
        
        List<Node> list = map.get(map.lastKey());
        
        Node node =  list.remove(list.size()-1);
        
        ddl.remove(node);
        
        if(list.isEmpty()){
            map.remove(map.lastKey());
        }
        
        return node.val;
        
    }
    
}



class DoubleLinkedList{
    Node head = null;
    Node tail = null;
        
    public DoubleLinkedList(){
            head = new Node(-1);
            tail = new Node(-1);
            head.next = tail;
            head.prev = null;
            
            tail.next = null;
            tail.prev = head;
    }
    
    public int add(Node node){
       
    
        node.next = tail;
        node.prev = tail.prev;
        tail.prev.next = node;
        tail.prev = node;
        
        return node.val;
        
    }
    
    public int peek(){
        return tail.prev.val;
    }
    
    
    public int pop(){
        Node t = tail.prev;
        
        tail.prev = t.prev;
        
        t.prev.next = t.next;
        t.next = null;
        t.prev = null;
        
        return t.val;
    }
    
    public int remove(Node node){
       System.out.println(node.prev.val);
        node.next.prev = node.prev;
        node.prev.next = node.next;
        
        node.next = null;
        node.prev = null;
        
        return node.val;
    }
        
}

class Node{
        
        public Node next;
        public Node prev;
        public int val;
        public Node(int x){
            this.val = x;
            next = null;
            prev = null;
        }
}

/**
 * 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();
 */

双stack，popMax是o(n),其他是o(1)

class MaxStack {
    private Stack<Integer> stack = null;
    private Stack<Integer> maxStack = null;
    
    /** initialize your data structure here. */
    public MaxStack() {
        stack = new Stack<>();
        maxStack = new Stack<>();
    }
    
    public void push(int x) {
        int max = maxStack.isEmpty() ? x : 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 = maxStack.peek();
        
        Stack<Integer> tmpStack = new Stack<>();
        
        while(max != stack.peek()) {
            tmpStack.push(pop());
        }
        
        pop();
        
        while(!tmpStack.isEmpty()){
            push(tmpStack.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();
 */

Max Stack - LeetCodeLeetCode