155. Min Stack

题目描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --
>
 Returns -3.
minStack.pop();
minStack.top();      --
>
 Returns 0.
minStack.getMin();   --
>
 Returns -2.

解题方法

//Using two stacks to implements the application

/*Using two stacks to implements the application

Runtime complexity: O\(n\)

Space complexity: O\(n\)\*/

//Using two stacks to implements the application
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack(){
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public void push(int x){
        if( minStack.isEmpty()){
            minStack.push(x);
        }else{
            if( x <= minStack.peek()){
                minStack.push(x);
            }
        }
        stack.push(x);
    }

    public void pop(){
        if( stack.peek().equals(minStack.peek())){
            minStack.pop();
        }
        stack.pop();
    }

    public int top(){
        return stack.peek();
    }

    public int getMin(){
        return minStack.peek();
    }

/\*Using Deque\(record the FILO order\) + minHeap the min value

O\(nlogn + n\) runtime complexity

O\(2n\) space complexity\*/

class MinStack {

    /** initialize your data structure here. */
    /*Using Deque(record the FILO order) + minHeap the min value
    O(nlogn + n) runtime complexity
    O(n) space complexity*/
    private Deque<Integer> deque;
    private PriorityQueue<Integer> minHeap;

    public MinStack() {
        deque = new ArrayDeque<>();
        minHeap = new PriorityQueue<>();
    }

    public void push(int x) {
        deque.offerLast(x);
        minHeap.offer(x);
    }

    public void pop() {
        if(!deque.isEmpty()){
            int x = deque.pollLast();
            minHeap.remove(x);
        }
    }

    public int top() {
        return deque.peekLast();
    }

    public int getMin() {
        return minHeap.peek();
    }
}