实现一个最小栈，有三种操作，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();
        }
    }
}