美文网首页
Leetcode: 155.Min Stack

Leetcode: 155.Min Stack

作者: bfx1000 | 来源:发表于2020-02-10 19:00 被阅读0次

    Question:

    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.
    

    Answer: two stacks

    Stack1 is an usual stack.

    Stack2 is the smallest element stack.

    Keeping top element of stack2 is smallest forever.

    pop the smallest element of stack2 at the same time with stack1.

    Code

    class MinStack {
        Stack<Integer> s1,s2;
        public MinStack(){
            s1=new Stack<>();
            s2=new Stack<>();
        }
        public void push(int x) {
            if(s2.isEmpty())
                s2.push(x);
            if(s2.peek()>x)
                s2.push(x);
            s1.push(x);
        }
        public void pop() {
            if(s1.peek()==s2.peek())
                s2.pop();
            s1.pop();
        }
        public int top() {
            return s1.peek();
        }
        public int getMin() {
            return s2.peek();
        }
    }
    

    相关文章

      网友评论

          本文标题:Leetcode: 155.Min Stack

          本文链接:https://www.haomeiwen.com/subject/gshzxhtx.html