0155.最小栈

难度：🟢 简单

标签：栈、设计

链接：155. 最小栈

题目描述

设计一个支持 push ，pop ，top 和 getMin 操作的最小栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。

• void push(int val) 将元素val推入堆栈。

• void pop() 删除堆栈顶部的元素。

• int top() 获取堆栈顶部的元素。

• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["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.

解题思路

核心思想

本题的核心挑战在于，需要在常数时间复杂度 O(1) 内完成 getMin 操作。如果只用一个普通的栈，每次获取最小值都需要遍历整个栈，时间复杂度为 O(n)。为了实现 O(1) 的查找，我们可以采用 “空间换时间” 的策略。

思路选择

辅助栈法 是解决此问题的经典思路。我们使用两个栈：

1. 一个主栈 stack，用于执行常规的 push, pop, top 操作。

2. 一个辅助栈 minStack，其栈顶永远保存着当前主栈中所有元素的最小值。

关键步骤

1. 初始化：创建两个空栈，stack 和 minStack。

2. push(val) 操作: a. 将 val 正常压入主栈 stack。 b. 检查 val 与 minStack 的栈顶元素。如果 minStack 为空，或者 val 小于等于 minStack 的栈顶元素，则也将 val 压入 minStack。这保证了 minStack 的栈顶始终是当前的最小值。

3. pop() 操作: a. 从主栈 stack 弹出一个元素。 b. 检查这个弹出的元素是否等于 minStack 的栈顶元素。如果是，说明当前最小值已经被弹出，那么 minStack 也需要同步弹出其栈顶元素，以更新最小值。

4. top() 操作: 直接返回主栈 stack 的栈顶元素。

5. getMin() 操作: 直接返回辅助栈 minStack 的栈顶元素，因为那里存放的就是当前最小值。

代码实现

var MinStack = function () {
    this.stack = [];
    this.minStack = []; // 辅助栈，栈顶始终为当前最小元素
};

/** * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
    this.stack.push(val);
    // 如果辅助栈为空，或新元素小于等于当前最小值，则推入辅助栈
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(val);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
    const poppedVal = this.stack.pop();
    // 如果弹出的值是当前最小值，则辅助栈也要弹出
    if (poppedVal === this.minStack[this.minStack.length - 1]) {
        this.minStack.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
    return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
    return this.minStack[this.minStack.length - 1];
};

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

复杂度分析

• 时间复杂度：O(1) push, pop, top, getMin 四个操作都只涉及对栈顶的访问，因此时间复杂度均为常数级别。

• 空间复杂度：O(n) 其中 n 是栈中元素的数量。在最坏的情况下（例如，推入的元素是严格递减的），minStack 需要存储所有 n 个元素。

相关题目

• 0232.用栈实现队列

• 0020.有效的括号

总结

本题是数据结构设计类的经典入门题。通过引入一个辅助栈，我们巧妙地解决了在 O(1) 时间内获取最小值的问题，这是“空间换时间”思想的绝佳体现。理解辅助栈如何与主栈同步，是掌握此题解法的关键。