1. 题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

2. 思路分析

有关栈的题目,可以考虑使用“辅助栈”,即利用空间换时间的方法。

这道题就是借助“辅助栈”来实现。当有新元素被 push 进普通栈的时候,程序比较新元素和辅助栈中的原有元素,选出最小的元素,将其放入辅助栈

根据栈的特点和操作思路,辅助栈顶的元素就是最小元素。并且辅助栈的元素和普通栈的元素是“一一对应”的。

3. 代码实现

/**
 * 包含Min函数的栈
 */
class MinStack {
  constructor() {
    this.stack = []; // 数据栈
    this.minStack = []; // 辅助栈
  }

  push(item) {
    const minLength = this.minStack.length;
    this.stack.push(item);

    if (minLength === 0) {
      // 初始情况: 直接放入
      this.minStack.push(item);
    } else {
      if (item < this.minStack[minLength - 1]) {
        // 新元素 < 辅助栈的最小元素: 将新元素放入
        this.minStack.push(item);
      } else {
        // 否则,为了保持2个栈的对应关系,放入辅助栈最小元素
        this.minStack.push(this.minStack[minLength - 1]);
      }
    }
  }

  pop() {
    if (this.stack.length === 0) {
      return null;
    }

    this.stack.pop();
    return this.minStack.pop();
  }

  min() {
    const minLength = this.minStack.length;
    if (minLength === 0) {
      return null;
    }

    return this.minStack[minLength - 1];
  }
}

/**
 * 以下是测试代码
 */

const minStack = new MinStack();

minStack.push(3);
minStack.push(4);
minStack.push(2);
minStack.push(1);
console.log(minStack.minStack, minStack.min()); // output: [ 3, 3, 2, 1 ] 1

minStack.pop();
minStack.pop();
minStack.push(0);
console.log(minStack.minStack, minStack.min()); // output: [ 3, 3, 0 ] 0
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62