30. 包含min函数的栈【辅助栈】

1. 问题

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.

提示：

  • 各函数的调用总次数不超过 20000 次

2. 解法 - 辅助栈

2.1 Java

class MinStack {
    /**
     * A为主栈，用于存储所有的元素
     * B为辅助栈，用于存储最小数
     */
    Stack<Integer> stackA, stackB;

    // 对两个栈进行初始化
    public MinStack() {
        stackA = new Stack<>();
        stackB = new Stack<>();
    }

    public void push(int x) {
        stackA.push(x);
        // 如果B为空，或者x比B的栈顶元素小，就把x压入B栈
        // 注意是小于等于哦！等于的时候也要压入，不然会漏
        if (stackB.empty() || x <= stackB.peek())
            stackB.push(x);
    }

    public void pop() {
        // 如果A的栈顶元素和B的栈顶元素（即当前的最小数）一致，那么A和B一起pop
        // 如果不一致，只要pop栈A中的栈顶元素即可，因为最小数此时没有发生改变
        //  注意：这里要用「equals」不能用「==」，仅当整数值处于[-128,127]之间可以使用「==」比较
        if (stackA.pop().equals(stackB.peek()))
            stackB.pop();
    }

    public int top() {
        return stackA.peek();
    }

    public int min() {
        return stackB.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

2.2 Kotlin

class MinStack {
    /**
     * A为主栈，用于存储所有的元素
     * B为辅助栈，用于存储最小数
     */
    var stackA: Stack<Int>
    var stackB: Stack<Int>

    // 对两个栈进行初始化
    init {
        stackA = Stack()
        stackB = Stack()
    }

    fun push(x: Int) {
        stackA.push(x)
        // 如果B为空，或者x比B的栈顶元素小，就把x压入B栈
        if (stackB.empty() || x <= stackB.peek())
            stackB.push(x)
    }

    fun pop() {
        // 如果A的栈顶元素和B的栈顶元素（即当前的最小数）一致，那么A和B一起pop
        // 如果不一致，只要pop栈A中的栈顶元素即可，因为最小数此时没有发生改变
        if (stackA.pop() == stackB.peek())
            stackB.pop()
    }

    fun top(): Int {
        return stackA.peek()
    }

    fun min(): Int {
        return stackB.peek()
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

2.3 复杂度分析

  • 时间复杂度 O(1) ： push(), pop(), top(), min() 四个函数的时间复杂度都属于常数级别。

  • 空间复杂度 O(N) ：辅助栈 B 最差情况下存储 N 个元素，需要使用 O(N) 的额外空间。

3. 参考

上一页29. 顺时针打印矩阵【模拟】下一页31. 栈的压入、弹出序列【辅助栈】

最后更新于