iis服务器助手广告广告
返回顶部
首页 > 资讯 > 前端开发 > JavaScript >前端算法之TypeScript包含min函数的栈实例详解
  • 815
分享到

前端算法之TypeScript包含min函数的栈实例详解

2024-04-02 19:04:59 815人浏览 泡泡鱼
摘要

目录前言思路梳理实现代码示例代码前言 基于数据结构: “栈”,实现一个min函数,调用此函数即可获取栈中的最小元素。在该栈中,调用min、push、pop的时

前言

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

本文就跟大家分享下这个算法,欢迎各位感兴趣的开发者阅读本文。

思路梳理

相信大多数开发者看到这个问题,第一反应可能是每次往栈中压入一个新元素时,将栈里的所有元素排序,让最小的元素位于栈顶,这样就能在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

以上就是前端算法之typescript包含min函数的栈实例详解的详细内容,更多关于TypeScript min函数栈的资料请关注编程网其它相关文章!

--结束END--

本文标题: 前端算法之TypeScript包含min函数的栈实例详解

本文链接: https://www.lsjlt.com/news/168409.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作