155.最小栈

发表于 分类于 阅读次数：

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

实现 MinStack 类：

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

你必须实现一个时间复杂度为 O(1) 的栈，而且还支持 getMin 操作。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["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.

解题思路

这是一道经典的设计题，考察对栈的理解和最小值的维护。

核心思想

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

方法一：双栈法（推荐）

时间复杂度 O(1)、空间复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * initialize your data structure here.
 */
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 popped = this.stack.pop();
    
    // 如果弹出的是最小值，也要从最小值栈中弹出
    if (popped === 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];
};

方法二：优化版本（存储差值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var MinStack = function() {
    this.stack = [];
    this.min = Infinity;
};

MinStack.prototype.push = function(val) {
    // 存储与最小值的差值
    this.stack.push(val - this.min);
    
    // 更新最小值
    if (val < this.min) {
        this.min = val;
    }
};

MinStack.prototype.pop = function() {
    const diff = this.stack.pop();
    
    // 如果差值小于0，说明这个元素是最小值
    if (diff < 0) {
        this.min = this.min - diff;
    }
};

MinStack.prototype.top = function() {
    const diff = this.stack[this.stack.length - 1];
    
    // 如果差值小于0，说明这个元素是最小值
    if (diff < 0) {
        return this.min;
    }
    
    return this.min + diff;
};

MinStack.prototype.getMin = function() {
    return this.min;
};

方法三：使用对象存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var MinStack = function() {
    this.stack = [];
};

MinStack.prototype.push = function(val) {
    const min = this.stack.length === 0 ? val : Math.min(this.getMin(), val);
    this.stack.push({ val, min });
};

MinStack.prototype.pop = function() {
    this.stack.pop();
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1].val;
};

MinStack.prototype.getMin = function() {
    return this.stack[this.stack.length - 1].min;
};

方法四：单栈法（存储元组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var MinStack = function() {
    this.stack = [];
};

MinStack.prototype.push = function(val) {
    const min = this.stack.length === 0 ? val : Math.min(this.getMin(), val);
    this.stack.push([val, min]);
};

MinStack.prototype.pop = function() {
    this.stack.pop();
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1][0];
};

MinStack.prototype.getMin = function() {
    return this.stack[this.stack.length - 1][1];
};

解题要点

  1. 双栈法：

    • 主栈存储所有元素
    • 最小栈存储当前最小值
    • 每次push时更新最小栈
    • 每次pop时检查是否需要更新最小栈

  2. 时间复杂度：

    • 所有操作都是O(1)
    • 空间复杂度O(n)

  3. 边界处理：

    • 空栈的情况
    • 重复最小值的情况

面试要点

  • 高频考点：这道题是面试中的高频设计题
  • 栈操作：考察对栈的基本操作的理解
  • 最小值维护：考察如何高效维护最小值
  • 时间复杂度：要求O(1)的操作复杂度

相关题目

扩展思考

  1. 为什么使用双栈法？

    • 主栈维护正常的栈操作
    • 最小栈维护当前的最小值
    • 两个栈同步操作，保证O(1)复杂度

  2. 时间复杂度分析

    • push操作：O(1)
    • pop操作：O(1)
    • top操作：O(1)
    • getMin操作：O(1)

  3. 空间复杂度优化

    • 双栈法：O(n)
    • 差值法：O(n)但常数更小
    • 对象法：O(n)

  4. 实际应用

    • 股票价格的最小值跟踪
    • 温度记录的最低温度
    • 游戏中的最低分数

  5. 变种问题

    • 支持getMax操作
    • 支持getMin和getMax
    • 支持范围查询

最后更新: 2021-09-21