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.
MinStack minStack = new MinStack();
minStack.getMin();   --> Returns -3.
minStack.pop();;      --> Returns 0.
minStack.getMin();   --> Returns -2.


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()){
    public void pop() {
    public int top() {
        return stack.peek();
    public int getMin() {
        return minStack.peek();
//comment line

No comments:

Post a Comment