Min Stack
Question
Solution
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.
Show Tags
Have you met this question in a real interview? Yes No
SOLUTION 1:
比较直观。用一个min stack专门存放最小值,如果有比它小 或是相等的(有多个平行的最小值都要单独存放,否则pop后会出问题),
则存放其到minstack.具体看代码:
class MinStack {
Stack<Integer> elements = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>(); public void push(int x) {
elements.push(x);
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
} public void pop() {
if (elements.isEmpty()) {
return;
} // 这个地方太蛋疼了,居然要用equals...
if (elements.peek().equals(minStack.peek())) {
minStack.pop();
}
elements.pop();
} public int top() {
return elements.peek();
} public int getMin() {
return minStack.peek();
}
}
2014.1229 redo.
class MinStack {
Stack<Integer> s = new Stack<Integer>();
Stack<Integer> min = new Stack<Integer>(); public void push(int x) {
s.push(x);
if (min.isEmpty() || x <= min.peek()) {
min.push(x);
}
} // Pop 1: use equals.
public void pop1() {
// BUG 1: Very very trick. we should use EQUALS here instead of "=="
if (s.peek().equals(min.peek())) {
min.pop();
}
s.pop();
} // Pop 2: use int
public void pop2() {
// BUG 1: Very very trick. we should use EQUALS here instead of "=="
int n1 = s.peek();
int n2 = min.peek();
if (n1 == n2) {
min.pop();
}
s.pop();
} // Pop 3: use (int)
public void pop() {
// BUG 1: Very very trick. we should use EQUALS here instead of "=="
if ((int)s.peek() == (int)min.peek()) {
min.pop();
}
s.pop();
} public int top() {
return s.peek();
} public int getMin() {
return min.peek();
}
}
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/stack/MinStack.java