Stack Min: How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.
Hints:#27, #59, #78
解答
如果在stack里放一个min属性用来跟踪min，那么push的时候min到还好说，但是pop的时候要把次min的恢复出来就麻烦了。
弄两个stack，一个正常存储value，另一个只存储min values。
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
|
public class StackMin {
private Stack<Integer> num = new Stack<>();
private Stack<Integer> min = new Stack<>();
public void push(Integer value) {
if (num.isEmpty()) {
num.push(value);
min.push(value);
return;
}
if (value <= min.peek()) {
// 只存比当前min更小的数字，这里用<=是为了应对连续push相同数字的情况
min.push(value);
}
num.push(value);
}
public Integer pop() {
Integer val = num.pop();
if (val.equals(min.peek())) {
// 如果pop了最小值，那么min也
min.pop();
}
return val;
}
public Integer min() {
return min.peek();
}
}
|
评论