[!info] related notes 算法面试题型 MOC 栈

最小栈

题目链接：https://leetcode.cn/problems/min-stack/

题型判断

这是典型设计题。

要求：

• 支持普通栈操作
• 还要 O(1) 拿到当前最小值

若普通栈只存原始值、每次 getMin 都重新扫描，会退化成 O(n)。也可在一个栈的每项中保存“值 + 前缀最小值”；本文采用两个同步栈。

核心思路

用两个栈：

• stack：正常存所有元素
• minStack：存“到当前位置为止的最小值”

这样：

• push(val) 时，同时把新的最小值压进 minStack
• pop() 时，两个栈一起弹
• getMin() 时，直接看 minStack 栈顶

JavaScript

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

    push(val) {
        this.stack.push(val);

        if (!this.minStack.length) {
            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(n)，getMin/top 为 O(1)，数组 push/pop 按摊销 O(1) 分析；题目保证查询和弹出时非空。