Min Stack

Medium Min Stack

29%

Accepted

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Have you met this question in a real interview? 

Yes

Example

Operations: push(1), pop(), push(2), push(3), min(), push(1), min() Return: 1, 2, 1

Note

min operation will never be called if there is no number in the stack

public class Solution {
    Stack<Integer> stack;
    int min;
    public Solution() {
        // do initialize if necessary
        stack = new Stack<Integer>();
    }

    public void push(int number) {
        // write your code here
        if(stack.isEmpty()) min = number;
        stack.push(number-min);
         if(number < min) min = number;
    }

    public int pop() {
        // write your code here
        int val = stack.pop();
        if(val < 0){
            min = min - val;
        }
        return val + min;
    }

    public int min() {
        // write your code here
        return min;
    }
}

public class Solution {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public Solution() {
        // do initialize if necessary
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public void push(int number) {
        // write your code here
        stack.push(number);
        if(minStack.isEmpty()) minStack.push(number);
        else if(minStack.peek() >= number) minStack.push(number);
    }

    public int pop() {
        // write your code here
        int val = stack.pop();
        if(val == minStack.peek()){
           minStack.pop();
        }
        return val;
    }

    public int min() {
        // write your code here
        return minStack.peek();
    }
}