1.20 Min Stack

Description

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. Show Company Tags Show Tags Show Similar Problems

Method

I will use two stack to implement a min stack. One stack is used to work as normal stack to contains numbers, and another stack is called Minstack used to keep the minmal val of all numbers that have already been pushed to normal stack

just like if i do push (3) push(5) the minStack has (3) stack (3, 5) and then if push(2) since it smaller than 3 it will be pushed into minStack(3, 2) so if I call min(), I get 2.

Time and Space Complexity

push : o(1) pop : o(1) top: o(1) min : o(1)

Code

public class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;

/** initialize your data structure here. */
public MinStack() {
     stack = new Stack<Integer>();
     minStack = new Stack<Integer>();
}

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

public void pop() {
    if (!stack.isEmpty()){
         int x = stack.peek();
         stack.pop();
         if (minStack.peek() == x){
             minStack.pop();
         }
    }

}

public int top() {
     int res = 0;
     if (!stack.isEmpty()){
         res = stack.peek();
     }
     return res;
}

public int getMin() {
     int res = 0;
     if (!minStack.isEmpty()){
         res = minStack.peek();
     }
     return res;
}

}

/**

• Your MinStack object will be instantiated and called as such:
• MinStack obj = new MinStack();
• obj.push(x);
• obj.pop();
• int param_3 = obj.top();
• int param_4 = obj.getMin(); */