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 ();
}
}
评论