包含min函数的栈

问题陈述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.

思路分析

普通栈的push和pop操作的时间复杂度为O(1)，但是获取min则需要遍历一遍，复杂度为O(n)。

如此，我们考虑使用一个辅助栈来实现。

主栈：用于存储所有元素，实现正常的出入栈操作，获取栈顶元素等。

辅助栈：用于另存入主栈元素出现的最小元素，如先存入第一个入主栈元素，后面入栈元素依次与之比较，若更小，则继续存入，确保最小元素永远在辅助栈的栈顶。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Min_Stack {
    public Stack<Integer> A,B;
    public Min_Stack(){
        A=new Stack<>();
        B=new Stack<>();
    }
    public void push(int x){
        A.add(x);
        if(B.isEmpty()||B.peek()>=x)//判断栈空只能用isEmpty，或者是peek=-1。不能用null
            B.add(x);
    }
    public void pop(){
        if(A.pop().equals(B.peek()))//每次弹出最小元素
            B.pop();
    }
    public int top(){
        return A.peek();
    }
    public int min(){
        return B.peek();
    }
}