155.最小栈

details

class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];
    }

    push(val) {
        this.stack.push(val);
        // If the minStack is empty or the new value is less than or equal to the current minimum, push it onto the minStack
        if (this.minStack.length === 0 || val <= this.getMin()) {
            this.minStack.push(val);
        }
    }

    pop() {
        // If the popped value is the same as the current minimum, pop it from the minStack as well
        if (this.stack.pop() === this.getMin()) {
            this.minStack.pop();
        }
    }

    top() {
        return this.stack.at(-1);
    }

    getMin() {
        return this.minStack.at(-1);
    }
}

// 测试用例
let minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
console.log(minStack.getMin()); // 返回 -3
minStack.pop();
console.log(minStack.top()); // 返回 0
console.log(minStack.getMin()); // 返回 -2

解释

1. 构造函数 MinStack:

   • this.stack 用于存储实际的栈元素。
   • this.minStack 用于存储最小值的辅助栈。

2. push(val) 方法:

   • 将 val 压入 stack。
   • 如果 minStack 为空或 val 小于等于当前的最小值，将 val 压入 minStack。

3. pop() 方法:

   • 如果弹出的元素是当前的最小值，也将其从 minStack 中弹出。

4. top() 方法:

   • 返回 stack 栈顶的元素。

5. getMin() 方法:

   • 返回 minStack 栈顶的元素，即当前的最小值。

复杂度分析

时间复杂度:

• 所有操作（push, pop, top, getMin）都是 O(1) 的时间复杂度，因为辅助栈操作与主栈同步。

空间复杂度:

• O(n)，其中 n 是栈中的元素个数。最坏情况下，minStack 中的元素个数与 stack 中的元素个数相同。