最小栈

🟡 中等

题目描述

设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。

示例

输入：
["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]
[[], [-2], [0], [-3], [], [], [], []]

输出：
[null, null, null, null, -3, null, 0, -2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3
minStack.pop();
minStack.top();      --> 返回 0
minStack.getMin();   --> 返回 -2

提示

-2^31 <= val <= 2^31 - 1
pop、top 和 getMin 操作总是在非空栈上调用

解法

参考答案 (2 个标签)

辅助栈 O(1)

思路

使用两个栈：一个存储数据，一个存储当前最小值。每次 push 时，同时更新最小栈。

代码实现

class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }
    
    push(val) {
        this.stack.push(val);
        if (this.minStack.length === 0) {
            this.minStack.push(val);
        } else {
            this.minStack.push(Math.min(val, this.minStack[this.minStack.length - 1]));
        }
    }
    
    pop() {
        this.stack.pop();
        this.minStack.pop();
    }
    
    top() {
        return this.stack[this.stack.length - 1];
    }
    
    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

复杂度分析

时间复杂度：所有操作 O(1)
空间复杂度：O(n)

图解

操作序列: push(-2), push(0), push(-3), pop(), push(1)

stack:    [-2] → [-2, 0] → [-2, 0, -3] → [-2, 0] → [-2, 0, 1]
minStack: [-2] → [-2, -2] → [-2, -2, -3] → [-2, -2] → [-2, -2, -2]

下一章节每日温度