05 August 2008
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Example:
1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
跟普通的栈相比，就多了一个取最小值的方法，使用两个栈，一个栈按顺序存储进来的数据，另外一个存出现过的最小值。
使用两个栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class MinStack {
private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
stack1.push(x);
if (stack2.empty() || stack2.peek() >= x) {//第二个栈存入最小值
stack2.push(x);
}
}
public void pop() {
//注意这里不能下面这样写，因为两个栈各自弹出的元素类型是object，两个不同的object比较会是false；得先转为int
// if (stack2.peek() == stack1.peek()) stack2.pop();
// stack1.pop();
//如果两个栈的顶部元素相等，那都要弹出，最小值不能只留在第二个栈里面
int x = stack1.pop();
if (stack2.peek() == x) {
stack2.pop(); // 仔细想想，因为push的顺序问题，只要stack1中还有元素，stack2中的最小值就不会pop完
}
}
public int top() {
return stack1.peek();
}
public int getMin() {
return stack2.peek();
}
}
/**
* 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();
*/
只用一个栈，需要一个整型变量min_val来记录当前最小值，初始化为整型最小值，然后如果需要进栈的数字小于等于当前最小值min_val，那么将min_val压入栈，并且将min_val更新为当前数字。在出栈操作时，先将栈顶元素移出栈，再判断该元素是否和min_val相等，相等的话我们将min_val更新为新栈顶元素，再将新栈顶元素移出栈即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MinStack {
private Stack<Integer> stack = new Stack<>();
private int min_val = Integer.MAX_VALUE;
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
// 把可能的倒数第二小的值存在第二位
if (x <= min_val) {
stack.push(min_val);
min_val = x;
}
stack.push(x);
}
public void pop() {
// 同样这里要pop两次，栈顶元素和可能的刚才第二小元素
if (stack.pop() == min_val) { // 如果不等于，说明之前倒数第二个元素不是倒数第二小
min_val = stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min_val;
}
}
/**
* 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();
*/