实现一个最小栈,有三种操作,min:得到栈中的最小值,push:在栈顶插入一个元素,pop:弹出栈顶元素,使这三种操作的时间复杂度都是O(1)

1
2
3
4
public class StackWithMin extends Stack<Integer> {
public Integer push(Integer item)
public Integer pop()
}

额外维护一个栈 minStack 用来随时获取当前最小值。

  • 对于 push(value) 判断当前 minStack 的 top 是否小于 value,如果小于就 minStack.push(value)
  • 对于 pop() 判断当前 minStack 的 top 是否等于 value,如果等于就 minStack.pop()
  • 实现一个获取最小值的函数 getMin() 用来完善上述的 top
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
public class StackWithMin extends Stack<Integer> {
Stack<Integer> stackMin;

public StackWithMin(){
stackMin = new Stack<Integer>();
}

public Integer push(Integer item){
if(item <= min()){
stackMin.push(item);
}
super.push(item);
return item;
}

public Integer pop(){
int value = super.pop();
if(value == min()){
stackMin.pop();
}
return value;
}

public Integer min(){
if(stackMin.isEmpty()){
return Integer.MAX_VALUE;
} else {
return stackMin.peek();
}
}
}