[宝宝也能看懂的活动篇][30-Day LeetCoding Challenge] 第十天

最小栈

Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列特别篇 - 官方小活动『30-Day LeetCoding Challenge』。

这里是 4 月 10 号的题，也是题目列表中的第 155 题 -- 『最小栈』

题目描述

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

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

官方难度

EASY

解决思路

题目要求很简单，就是要封装一个叫做 MinStack 的类，几个操作都是普通的栈操作，不过多了一个返回最小的元素值。由于原生 JS 的 Array 就集合了队列和栈的操作行为，所以我们可以直接基于它来实现。

直接方案

直接基于原生的 Array 来实现栈的操作，另外我们用一个变量来记录栈内数据的最小值。这里小猪用一个 _top 指针来标识栈顶的位置，从而避免数据的擦除开销和数组动态缩短的开销，另外在每一次 pop 的时候通过遍历去更新记录的最小值。具体代码如下：

class MinStack {
  constructor() {
    this._top = -1;
    this.data = [];
    this.min = Number.MAX_SAFE_INTEGER;
  }
  push(n) {
    this.data[++this._top] = n;
    n < this.min && (this.min = n);
  }
  pop() {
    this.min = Number.MAX_SAFE_INTEGER;
    for (let i = --this._top; i >= 0; --i) {
      this.data[i] < this.min && (this.min = this.data[i]);
    }
  }
  top() {
    return this.data[this._top];
  }
  getMin() {
    return this.min;
  }
}

优化

上述代码有个问题，pop 操作的时间复杂度其实是 O(n)，因为需要通过遍历来完成最小值的更新。我们来尝试把它变成 O(1)。

为了直接更新最小值，那么它可能来自于可以直接计算或者提前算好了存起来。由于数据并没有什么数学联系，所以直接计算显然是不现实的，那么我们就从提前算好来考虑。我们可以想象一下在插入一个新数据的时候发生的情况：当前栈中的最小值我是知道的；新数据是否最小我也是知道的。那么就相当于插入数据前的最小值和插入数据后的最小值我都知道。那么反过来，它们其实也就是弹出数据前和弹出数据后的最小值。

到此，我们便得到了实现思路。具体代码如下：

class MinStack {
  constructor() {
    this._top = -1;
    this.data = [];
    this.min = Number.MAX_SAFE_INTEGER;
  }
  push(n) {
    this.data[++this._top] = this.min;
    this.data[++this._top] = n;
    n < this.min && (this.min = n);
  }
  pop() {
    this.min = this.data[--this._top];
    --this._top;
  }
  top() {
    return this.data[this._top];
  }
  getMin() {
    return this.min;
  }
}