12 · Min Stack - LintCode
# Description
Implement a stack with following functions:
push(val)
push val into the stackpop()
pop the top element and return itmin()
return the smallest number in the stack
All above should be in O(1) cost
min()
will never be called when there is no number in the stack.
# Example
Example 1:
Input:
push(1)
min()
push(2)
min()
push(3)
min()
Output:
1
1
1
# Code
public class MinStack { | |
private Stack<Integer> stack; | |
private Stack<Integer> minStack; | |
public MinStack() { | |
stack = new Stack<>(); | |
minStack = new Stack<>(); | |
} | |
/* | |
* @param number: An integer | |
* @return: nothing | |
*/ | |
public void push(int number) { | |
stack.push(number); | |
if (minStack.isEmpty()) { | |
minStack.push(number); | |
} else { | |
int min = Math.min(minStack.peek(), number); | |
minStack.push(min); | |
} | |
} | |
/* | |
* @return: An integer | |
*/ | |
public int pop() { | |
minStack.pop(); | |
return stack.pop(); | |
} | |
/* | |
* @return: An integer | |
*/ | |
public int min() { | |
return minStack.peek(); | |
} | |
/* | |
public int top() { | |
return stack.peek(); | |
} | |
*/ | |
} |