前端算法之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函数栈的资料请关注我们其它相关文章！
相关推荐
-
TypeScript获取二叉树的镜像实例
目录 前言 思路分析 实现代码 前言 给定一颗二叉树,如何获取它的镜像?本文将跟大家分享这个问题的解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 当我们把一张写有文字的纸放在镜子前面,你看到的内容正好与你写的内容是相反的.那么我们就可以依据照镜子的经验画出它的镜像了,如下所示: 镜像前后的两棵树根节点相同 镜像后的树与镜像前相比:它们的左.右子节点交换了位置 通过观察后,我们就得出了一颗树的镜像过程:先序遍历这棵树的每个节点,如果遍历到的节点有子节点,就交换它的两个子节点.当交换完所有非叶
-
TypeScript 内置高级类型编程示例
目录 TypeScript 类型编程 TypeScript 内置高级类型 Pick<Type, Keys> Exclude<UnionType, ExcludedMembers> ReturnType<Type> 更多类型体操学习 TypeScript 类型编程 TypeScript 的类型系统,最基本的是简单对应 JavaScript 的 基本类型,比如 string.number.boolean 等,然后是新增的 tuple.enum.复合类型.交叉类型.索引类型等
-
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
-
详解Anyscript开发指南绕过typescript类型检查
目录 前言 场景设定 解决方法 注释忽略 场景用例 类型断言 场景用例 泛型转换 场景用例 总结 前言 随着越来越多的前端项目采用 typescript 来开发,越来越多前端开发者会接触.使用这门语言.它是前端项目工程化的一个重要帮手,结合 vscode 编辑器,给予了前端开发者更严谨.高效的编码体验.但同时,严格的类型检查也会使部分开发者的编码效率有所降低,将时间花费在解决类型冲突.类型不匹配上,从而导致望而却步,迟迟不敢上手. 本文描述了几种绕过 typescript 类型检查的方法,帮助t
-
TypeScript数组实现栈与对象实现栈的区别详解
目录 前言 数组实现栈 实现思路 实现代码 编写测试代码 对象实现栈 实现代码 编写测试代码 二者的区别 十进制转二进制 前言 栈作为一种数据结构,它可以应用在很多地方,当你需要经常获取刚存放进去的数据时,那么栈这种数据结构将是你的首选. 栈的实现方式一般有两种:数组实现和对象实现,这两种实现方式最终实现的功能都是一样的,但是在性能上却有着很大的差别. 本文将详细讲解这两种实现方式的差异并用TypeScript将其实现,欢迎各位感兴趣的开发者阅读本文. 数组实现栈 本文讲解的是栈用代码的实现,如
-
前端算法之TypeScript包含min函数的栈实例详解
目录 前言 思路梳理 实现代码 示例代码 前言 基于数据结构: “栈”,实现一个min函数,调用此函数即可获取栈中的最小元素.在该栈中,调用min.push.pop的时间复杂度都是O(1). 本文就跟大家分享下这个算法,欢迎各位感兴趣的开发者阅读本文. 思路梳理 相信大多数开发者看到这个问题,第一反应可能是每次往栈中压入一个新元素时,将栈里的所有元素排序,让最小的元素位于栈顶,这样就能在O(1)的时间内得到最小元素了.但这种思路不能保证最后入栈的元素能够最先出栈,因此这个思路行不通. 紧接着,我
-
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 异步协程函数原理及实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一. asyncio 1.python3.4开始引入标准库之中,内置对异步io的支持 2.asyncio本身是一个消息循环 3.步骤: (1)创建消息循环 (2)把协程导入 (3)关闭 4.举例: import threading # 引入异步io包 import asyncio # 使用协程 @ asyncio.coroutine def