我们一起聊聊包含min函数的栈

前言

基于数据结构: “栈”，实现一个min函数，调用此函数即可获取栈中的最小元素。在该栈中，调用min、push、pop的时间复杂度都是O(1)。

成都创新互联公司联系热线：18982081108，为您提供成都网站建设网页设计及定制高端网站建设服务，成都创新互联公司网页制作领域10年，包括成都水电改造等多个行业拥有多年的网站设计经验，选择成都创新互联公司，为网站保驾护航。

思路梳理

相信大多数开发者看到这个问题，第一反应可能是每次往栈中压入一个新元素时，将栈里的所有元素排序，让最小的元素位于栈顶，这样就能在O(1)的时间内得到最小元素了。但这种思路不能保证最后入栈的元素能够最先出栈，因此这个思路行不通。

紧接着，我们可能会想到用一个变量来存放最小的元素，每次压入一个新元素入栈时，如果它比当前最小的元素还要小，则更新最小元素。这样子做目的是达到了，但是又会有另一个问题：如果当前最小元素被弹出栈了，那么如何得到下一个最小的元素？

很显然，我们仅仅添加一个变量用来存储最小元素是不够的，也就是说当最小元素被取出时，我们希望得到次最小元素。那么，我们能否用一个辅助栈专门来存放这些最小元素呢？当元素入栈时，我们就取出辅助栈中的栈顶元素将其与新加入元素做大小比较，把较小的一方压入辅助栈中。

我们通过一个例子来讲解下这个过程，如下所示：

const stack = [
  3,
  5,
  7
  12,
  1,
  9,
  0
]

入栈过程如下图所示：

出栈时，我们同时弹出两个栈的栈顶元素，获取最小元素时，我们将辅助栈的栈顶元素返回即可，过程如下图所示：

实现代码

经过前面的分析，我们已经得出了完整的思路，接下来就是编码环节了，如下所示：

export class StackContainingMinFunction extends Stack {
  private minStack: Stack;
  private dataStack: Stack;

  constructor() {
    super();
    this.minStack = new Stack();
    this.dataStack = new Stack();
  }

  public push(item: number): void {
    this.dataStack.push(item);
    if (this.minStack.size() > 0) {
      const minVal = this.minStack.peek();
      // 比较当前入栈元素与minStack中的最小元素，将小的一方入minStack
      item > minVal ? this.minStack.push(minVal) : this.minStack.push(item);
      return;
    }
    this.minStack.push(item);
  }

  public pop(): void {
    this.minStack.pop();
    this.dataStack.pop();
  }

  public min(): number | null {
    if (this.minStack.size() > 0) return this.minStack.peek();
    return null;
  }
}

注意：上述代码继承了Stack，我们在之前文章中已经实现了它，对此感兴趣的开发者请移步：数组实现栈与对象实现栈的区别

我们将上个章节的例子代入上述实现的函数中，来看下它能否正确运行。

const stackMinFn = new StackContainingMinFunction();
stackMinFn.push(3);
stackMinFn.push(5);
stackMinFn.push(7);
stackMinFn.push(12);
stackMinFn.push(1);
stackMinFn.push(9);
stackMinFn.push(0);
stackMinFn.pop();
stackMinFn.pop();
stackMinFn.pop();
console.log("当前栈内最小值为:", stackMinFn.min());

示例代码

本文所列举的代码完整版请移步：

StackContainingMinFunction.ts
stackContainingMinFunction-test.ts

本文标题：我们一起聊聊包含min函数的栈
标题网址：http://www.shufengxianlan.com/qtweb/news45/89195.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容