[Leetcode] 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.

Solution:

用两个stack，一个stack用来存储值，一个stack用来维护在当前栈中的最小值。

class MinStack {
        Stack<Integer> vals=new Stack<Integer>();
        Stack<Integer> mins=new Stack<Integer>();
        public void push(int x) {
            vals.push(x);
            if(!mins.isEmpty()){
                int temp=mins.peek();
                if(temp>=x){　　　　　　//注意此处！！！在temp=x的时候也要push进去！！！想想[2,0,3,0]
                    mins.push(x);
                }
            }else{
                mins.push(x);
            }
        }

        public void pop() {
            if(!vals.isEmpty()){
                int x=vals.pop();
                if(!mins.isEmpty()){
                    if(x==mins.peek()){
                        mins.pop();
                    }
                }else{
                    return;
                }
            }else{
                return;
            }
        }

        public int top() {
            if(!vals.isEmpty()){
                return vals.peek();
            }else{
                return 0;
            }
        }

        public int getMin() {
            if(!mins.isEmpty()){
                return mins.peek();
            }else{
                return 0;
            }
        }
    }