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.
Note that all the operations have to be constant time operations.
Questions to ask the interviewer :
Q: What should getMin() do on empty stack?
A: In this case, return -1.
Q: What should pop do on empty stack?
A: In this case, nothing.
Q: What should top() do on empty stack?
A: In this case, return -1
NOTE : If you are using your own declared global variables, make sure to clear them out in the constructor.
Solution:
Time: N/A Space: O(n)
class Solution {
private Deque<Integer> stack = new ArrayDeque<>();
private Deque<Integer> minStack = new ArrayDeque<>();
public void push(int x) {
stack.push(x);
if (minStack.isEmpty()) {
minStack.push(x);
} else {
int curMin = minStack.peekFirst();
if (x < curMin) {
minStack.push(x);
} else {
minStack.push(curMin);
}
}
}
public void pop() {
if (stack.isEmpty()) return;
stack.pop();
minStack.pop();
}
public int top() {
if (stack.isEmpty()) return -1;
return stack.peekFirst();
}
public int getMin() {
if (minStack.isEmpty()) return -1;
return minStack.peekFirst();
}
}
class MinStack {
private Deque<Integer> stack;
private Deque<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new ArrayDeque();
minStack = new ArrayDeque();
}
public void push(int x) {
stack.push(x);
if (minStack.isEmpty()) {
minStack.push(x);
} else if (x < minStack.peekFirst()) {
minStack.push(x);
} else {
minStack.push(minStack.peekFirst());
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peekFirst();
}
public int getMin() {
return minStack.peekFirst();
}
}
/**
* 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();
*/