面试题30. 包含min函数的栈｜刷题打卡

一、题目描述：

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

示例：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.min();   --> 返回 -3.

minStack.pop();

minStack.top();      --> 返回 0.

minStack.min();   --> 返回 -2.

注意：

各函数的调用总次数不超过 20000 次。

二、思路分析：

实现一个栈包含栈的push、pop、min、top。从此可以看出需要创建一个MinStack类，类中包含以上四个方法。

可以使用两个栈实现min函数栈。一个存放正常的元素栈（element）,一个存放最小元素的栈（smallest）。 最小元素栈从大到小排列。

咱们先挑简单的实现。

top：

返回元素栈顶即可。（this.element[this.element.length - 1]）

min：

min方法返回的是当前元素栈中最小的值。直接返回最小栈中的栈顶即可。（this.smallest[this.smallest.length - 1]）

push：

对于入栈，可以使用一个元素栈存放正常的元素顺序。

方法一：

在最小栈中，

• 最小栈为空。直接将当前元素push到最小栈中；
• 不为空，判断存放的当前值与当前最小栈的栈顶元素：小于等于，执行压栈操作。

例：

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

方法二：最小栈的长度和元素栈一样。

• 最小栈为空。直接将当前元素push到最小栈中；
• 最小栈不为空。 当前元素小于等于最小栈栈顶元素，将当前元素压入最小栈；大于，将当前最小栈栈顶元素再一次入栈。

例：

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

pop：

方法一：

采用push方法一后，在考虑出栈的时候，需要判断当前最小栈栈顶是否等于当前元素的栈顶元素。 如果相等，在元素栈出栈时，最小栈也需要执行相应出栈操作。例：

minStack.pop();

minStack.pop();

方法二：沿用push方法二：元素出栈时，因为最小栈和元素栈长度相同，所以最小栈也执行相应出栈操作即可。

例：

minStack.pop();

minStack.pop();

三、AC 代码：

// 法一
class MinStack {
    element: number[];
    smallest: number[];
    constructor() {
        this.element = [];
        this.smallest = [];
    }
    push(x: number): void {
        this.element.push(x);
        if (!this.smallest.length) {
            this.smallest.push(x);
        } else {
            if (this.smallest[this.smallest.length - 1] >= x) {
                this.smallest.push(x);
            }
        }
    }
    pop(): void {
        this.smallest[this.smallest.length - 1] === this.element.pop() && this.smallest.pop();
    }
    top(): number {
        return this.element[this.element.length - 1];
    }
    min(): number {
        return this.smallest[this.smallest.length - 1];
    }
}
// 法二
push(num: number) {
    this.element.push(num);
    if (!this.smallest.length) {
      this.smallest.push(num);
    } else if (this.smallest[this.smallest.length - 1] >= num) {
      this.smallest.push(num);
    } else {
      this.smallest.push(this.smallest[this.smallest.length - 1]);
    }
  }
pop() {
    this.element.pop();
    this.smallest.pop();
  }

四、总结：

考察对栈的基本实现功能。此题属于简单题，对于栈的原理理解，基本可以做出来。

作者：ClyingDeng

链接：https://juejin.cn/post/6948977107766607879

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。