略
题目：定义栈的数据结构,在该类型中实现一个能够得到栈的最小元素的min函数,调用min,push及pop的时间复杂度为O(1)
分析
错误的解法
在自定义Stack中加入一个变量minNum用于存储最小值,每当插入值时,就和那个值比较,如果比minNum要小,则把该值赋给minNum,最后使用min()方法return这个minNum的值.
代码如下:
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
| public class MyStack extends Stack<Integer> {
private static Integer minNum = null;
@Override
public synchronized Integer pop() {
return super.pop();
}
@Override
public Integer push(Integer item) {
if (minNum == null){
minNum = item;
} else {
if ( item < minNum ){
minNum = item;
}
}
return super.push(item);
}
public Integer min(){
return minNum;
}
}
|
正确的解法
但是上述解法存在一个问题,minNnm保存的是曾经栈内最小的值,一旦该值出栈了,min()返回的依然是那个最小值,这不符合该题目的意思,算法出现了bug.
但是如何解决呢,由于时间复杂度要求为O(1),所以min()方法不能通过遍历栈来实现,这里可以使用另外一个辅助栈来实现,这个栈专门用来保存最小值,入栈时,如果值比辅助栈栈顶的值小,则入栈;出栈时,如果出栈的值等于辅助栈栈顶的值,则辅助栈也同样出栈操作,min()函数返回值是辅助栈的栈顶的值即可.
代码实现
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
| public class MyStackTwo extends Stack<Integer> {
Stack<Integer> stack = new Stack<>();
@Override
public synchronized Integer pop() {
if (!stack.isEmpty()){
Integer b = stack.pop();
if (b != lastElement()){
stack.push(b);
}
}
return super.pop();
}
@Override
public Integer push(Integer item) {
if (stack.isEmpty()){
stack.push(item);
} else {
Integer a = stack.lastElement();
if (a > item){
stack.push(item);
}
}
return super.push(item);
}
public Integer min(){
return stack.pop();
}
}
|
总结
当一个算法要求时间复杂度很小时,可以考虑采用开辟更大的空间来实现,例如本题中采用一个辅助栈来保存最小值.