题目

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

要求

  1. pop、push、getMin操作的时间复杂度都是O(1)。
  2. 设计的栈类型可以使用现成的栈结构。

难度

★☆☆☆

解答思路

  • 压入数据规则

    在设计上使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用于保存每一步的最小值，这个栈记为stackMin。具体的实现方式如下：

    假设当前数据为newNum，先将其压入stackData，然后判断stackMin是否为空：

    • 如果为空，则newNum也压入stackMin。
    • 如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：
      • 如果newNum更小或两者相等，则newNum也压入stackMIn；
      • 如果stackMin中栈顶元素小，则stackMin不压入任何内容。

  • 弹出数据规则

    先在stackData中弹出栈顶元素，记为value。然后比较当前stackMin的栈顶元素和value哪一个更小。

    由压入规则可知，stackMin中存在的元素是从栈底到栈顶逐渐变小的，stackMin栈顶的元素既是stackMin栈的最小值，也是当前stackData的最小值。

    当value等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value大于stackMin的栈顶元素时，stackMin不弹出栈顶元素；返回value。

  • 查询当前栈中的最小值操作

    由上可知，stackMin始终记录着stackData中的最小值，所以，stackMin的栈顶元素始终是当前stackData中的最小值。

代码实现如下：

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
class MyStack {
  constructor() {
    this.stackData = []
    this.stackMin = []
  }

  push(newNum) {
    this.stackData.push(newNum)

    if (!this.stackMin.length) {
      this.stackMin.push(newNum)
    } else if (newNum <= this.getMin()) {
      this.stackMin.push(newNum)
    }
  }

  pop() {
    if (!this.stackMin.length) {
      throw new Error('Your stack is empty.')
    }

    const value = this.stackData.pop()
    if (value === this.getMin()) {
      this.stackMin.pop()
    }
    return value
  }

  getMin() {
    if (!this.stackMin.length) {
      throw new Error('Your stack is empty.')
    }
    return this.stackMin[this.stackMin.length - 1]
  }
}