Wednesday, April 19, 2017

Min Stack

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.

Thoughts:

The key to this question lies in the design of minStack, push () pop () top () These operations are built-in Java Stack, do not have to say about it.  The minStack record is always the smallest of all current elements, regardless of where minStack.peek () is in the stack.

Push(): When a new element is smaller than previous one, add it to minStack. The normal stack should keep adding new elements.

Pop(): Compare the two objects,  pop from minStack and normal stack if they are equal.  If not, always pop from the normal stack.

Java Solution:
public class MinStack {
    private Stack stack;
    private Stack minStack;
    public MinStack() {
        stack = new Stack();
        minStack = new Stack();
    }
    
    public void push(int x) {
        if(minStack.isEmpty() || 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();
    }
}
//comment line

No comments:

Post a Comment