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

目录
  • 前言
  • 思路梳理
  • 实现代码
  • 示例代码

前言

基于数据结构: “栈”，实现一个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());

示例代码

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

以上就是前端算法之TypeScript包含min函数的栈实例详解的详细内容，更多关于TypeScript min函数栈的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 详解Anyscript开发指南绕过typescript类型检查

    详解Anyscript开发指南绕过typescript类型检查

    目录 前言 场景设定 解决方法 注释忽略 场景用例 类型断言 场景用例 泛型转换 场景用例 总结 前言 随着越来越多的前端项目采用 typescript 来开发,越来越多前端开发者会接触.使用这门语言.它是前端项目工程化的一个重要帮手,结合 vscode 编辑器,给予了前端开发者更严谨.高效的编码体验.但同时,严格的类型检查也会使部分开发者的编码效率有所降低,将时间花费在解决类型冲突.类型不匹配上,从而导致望而却步,迟迟不敢上手. 本文描述了几种绕过 typescript 类型检查的方法,帮助t

  • TypeScript实用技巧 Nominal Typing名义类型详解

    TypeScript实用技巧 Nominal Typing名义类型详解

    目录 Nominal Typing(名义类型) 概念解析 拓展应用 在Vue中的应用 Nominal Typing(名义类型) 概念解析 意思是给一个类型附加上一个“名义”,从而防止结构类型在某些情况下由于类型结构相似而被错用.假设有如下代码: interface Vector2D { x: number, y: number }; interface Vector3D { x: number, y: number, z: number }; function calc(vector: Vect

  • TypeScript数组实现栈与对象实现栈的区别详解

    TypeScript数组实现栈与对象实现栈的区别详解

    目录 前言 数组实现栈 实现思路 实现代码 编写测试代码 对象实现栈 实现代码 编写测试代码 二者的区别 十进制转二进制 前言 栈作为一种数据结构,它可以应用在很多地方,当你需要经常获取刚存放进去的数据时,那么栈这种数据结构将是你的首选. 栈的实现方式一般有两种:数组实现和对象实现,这两种实现方式最终实现的功能都是一样的,但是在性能上却有着很大的差别. 本文将详细讲解这两种实现方式的差异并用TypeScript将其实现,欢迎各位感兴趣的开发者阅读本文. 数组实现栈 本文讲解的是栈用代码的实现,如

  • TypeScript 内置高级类型编程示例

    TypeScript 内置高级类型编程示例

    目录 TypeScript 类型编程 TypeScript 内置高级类型 Pick<Type, Keys> Exclude<UnionType, ExcludedMembers> ReturnType<Type> 更多类型体操学习 TypeScript 类型编程 TypeScript 的类型系统,最基本的是简单对应 JavaScript 的 基本类型,比如 string.number.boolean 等,然后是新增的 tuple.enum.复合类型.交叉类型.索引类型等

  • TypeScript获取二叉树的镜像实例

    TypeScript获取二叉树的镜像实例

    目录 前言 思路分析 实现代码 前言 给定一颗二叉树,如何获取它的镜像?本文将跟大家分享这个问题的解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 当我们把一张写有文字的纸放在镜子前面,你看到的内容正好与你写的内容是相反的.那么我们就可以依据照镜子的经验画出它的镜像了,如下所示: 镜像前后的两棵树根节点相同 镜像后的树与镜像前相比:它们的左.右子节点交换了位置 通过观察后,我们就得出了一颗树的镜像过程:先序遍历这棵树的每个节点,如果遍历到的节点有子节点,就交换它的两个子节点.当交换完所有非叶

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

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

    目录 前言 思路梳理 实现代码 示例代码 前言 基于数据结构: “栈”,实现一个min函数,调用此函数即可获取栈中的最小元素.在该栈中,调用min.push.pop的时间复杂度都是O(1). 本文就跟大家分享下这个算法,欢迎各位感兴趣的开发者阅读本文. 思路梳理 相信大多数开发者看到这个问题,第一反应可能是每次往栈中压入一个新元素时,将栈里的所有元素排序,让最小的元素位于栈顶,这样就能在O(1)的时间内得到最小元素了.但这种思路不能保证最后入栈的元素能够最先出栈,因此这个思路行不通. 紧接着,我

  • C语言之包含min函数的栈实例详解

    C语言之包含min函数的栈实例详解

    目录 一.题目描述 二.思路分析 三.整体代码 总结 一.题目描述 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min.push 及 pop 的时间复杂度都是 O ( 1 ) \rm{O(1)} O(1). 示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回-3. m

  • Python实现包含min函数的栈

    本文实例讲述了Python实现包含min函数的栈.分享给大家供大家参考,具体如下: # coding=utf8 ''' 题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数. 在该栈中,调用min.push及pop的时间复杂度都是O(1). ''' class Stack(): def __init__(self): self.main_stack = [] # 辅助栈,每次次最小的元素压入辅助栈 self.assist_stack = [] # 记录栈中的最小元素 se

  • C语言中qsort函数的用法实例详解

    C语言中qsort函数的用法实例详解 快速排序是一种用的最多的排序算法,在C语言的标准库中也有快速排序的函数,下面说一下详细用法. qsort函数包含在<stdlib.h>中 qsort函数声明如下: void qsort(void * base,size_t nmemb,size_t size ,int(*compar)(const void *,const void *)); 参数说明: base,要排序的数组 nmemb,数组中元素的数目 size,每个数组元素占用的内存空间,可使用si

  • C++中回调函数及函数指针的实例详解

    C++中回调函数及函数指针的实例详解 如何获取到类中函数指针 实现代码: //A类与B类的定义 class A { public: void Test() { cout << "A::Test()" << endl; } }; class B : public A { public: void Test() { cout << "B::Test()" << endl; } }; //定义类的成员函数指针 typedef

  • ES6中Array.copyWithin()函数的用法实例详解

    ES6为Array增加了copyWithin函数,用于操作当前数组自身,用来把某些个位置的元素复制并覆盖到其他位置上去. Array.prototype.copyWithin(target, start = 0, end = this.length) 该函数有三个参数. target:目的起始位置. start:复制源的起始位置,可以省略,可以是负数. end:复制源的结束位置,可以省略,可以是负数,实际结束位置是end-1. 例: 把第3个元素(从0开始)到第5个元素,复制并覆盖到以第1个位置

  • web前端vue之vuex单独一文件使用方式实例详解

    Vuex 是什么? Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式.它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化.Vuex 也集成到 Vue 的官方调试工具 devtools extension,提供了诸如零配置的 time-travel 调试.状态快照导入导出等高级调试功能. 上次我用了一个加减的例子为大家讲解vuex的基本的使用方式,和在什么样的情况下使用.上次还是在一个组件内把这个例子简单的展示了下,这次我把vuex抽离出来一个

  • C语言中access/_access函数的使用实例详解

    在Linux下,access函数的声明在<unistd.h>文件中,声明如下: int access(const char *pathname, int mode); access函数用来判断指定的文件或目录是否存在(F_OK),已存在的文件或目录是否有可读(R_OK).可写(W_OK).可执行(X_OK)权限.F_OK.R_OK.W_OK.X_OK这四种方式通过access函数中的第二个参数mode指定.如果指定的方式有效,则此函数返回0,否则返回-1. 在Windows下没有access函

  • nodejs中函数的调用实例详解

    一.调用本js文件中的函数 var http = require('http'); http.createServer(function (request,response){ response.writeHead(200, {'Contet-Type':'text/html;charset=utf-8'}); if(request.url!=='/favicon.ico'){ funl(response); response.end(''); } }).listen(8000); consol

  • Python 异步协程函数原理及实例详解

    Python 异步协程函数原理及实例详解

    这篇文章主要介绍了Python 异步协程函数原理及实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一. asyncio 1.python3.4开始引入标准库之中,内置对异步io的支持 2.asyncio本身是一个消息循环 3.步骤: (1)创建消息循环 (2)把协程导入 (3)关闭 4.举例: import threading # 引入异步io包 import asyncio # 使用协程 @ asyncio.coroutine def

随机推荐