最小栈

设计类栈题：用辅助栈同步维护每个位置之前的最小值，从而在 O(1) 时间返回最小元素。

#resource / algorithm #type / snippet #status / evergreen #source / leetcode #ds / stack

[!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];
    }
}

一句话总结

辅助栈不是只存“更小值出现的时刻”，而是存“每一层对应的历史最小值”。