Use an extra stack to keep track of the current minimum value. During the push operation we choose the new element or the current minimum, whichever that is smaller to push onto the min stack.
O(n) runtime, O(n) space – Minor space optimization:
If a new element is larger than the current minimum, we do not need to push it on to the min stack. When we perform the pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the min stack too.
public class MinStack {
/** initialize your data structure here. */
public MinStack() {}
private Stack<Integer> stack = new Stack<>();
private Stack<Integer> minstack = new Stack<>();
public void push(int x) {
if(minstack.isEmpty() || x <= minstack.peek()) {
minstack.push(x);
}
stack.push(x);
}
public void pop() {
if(minstack.peek().equals(stack.peek())) {
minstack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minstack.peek();
}
}
/**
Your MinStack object will be instantiated and called as such:
Shawngbk
commented
8 years ago
O(n) runtime, O(n) space – Extra stack:
Use an extra stack to keep track of the current minimum value. During the push operation we choose the new element or the current minimum, whichever that is smaller to push onto the min stack. O(n) runtime, O(n) space – Minor space optimization:
If a new element is larger than the current minimum, we do not need to push it on to the min stack. When we perform the pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the min stack too.
public class MinStack {
}
/**