前额叶是大脑控制中枢。
人类是所有动物中,唯一能够自主控制自己的欲望、情绪和冲动的动物,能够为了将来更大的利益而延迟满足当下的需求。
大家好,我是柒八九。
今天,我们继续探索JS算法相关的知识点。我们来谈谈关于{栈| Stack}的相关知识点和具体的算法。
如果,想了解其他数据结构的算法介绍,可以参考我们已经发布的文章。如下是算法系列的往期文章。
文章list
好了,天不早了,干点正事哇。
文章概要
- 知识点简讲
- 后缀表达式
- 小行星碰撞
- 判断括号的正确性
- 每日温度
- 直方图最大面积
知识点简讲
栈是个啥
栈是一种遵从后进先出(LIFO
)原则的有序集合。新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。
栈也被用在编程语言的编译器和内存中保存变量、方法调用等,也被用于浏览器历史记录(浏览器的返回按钮)。
而在前端,Stack
耳熟能详的功能就是调用栈,调用栈就是用来管理函数调用关系的一种数据结构,是 JavaScript
引擎追踪函数执行的一个机制。
还有一个比较重要的用处就是在解析器中,无论是HTML
/Vue
/JavaScript
,在生成对应的AST
的时候,针对Token
进行匹配处理。此时,就可以利用Stack
后进先出的特性,进行匹配处理。
解析HTML生成的AST
解析Vue模板生成的AST
关于调用栈的详细介绍,可以翻阅我们之前文章。这里就不在赘述。
栈的应用(算法方向)
在一些题目中,数据保存的顺序和使用顺序相反,即最后保存的数据最先使用,这与栈的后进先出特性契合,可以将数据保存到栈中。
JS版本的Stack
由于JS语言的特殊性,不存在真正意义上的Stack
结构,一般使用数组特定的Api
(push/pop
)模拟最简单的stack
使得能够满足后进先出的特性。
let stack = []; stack.push(1); stack.push(2); ==== 入栈 1、2==== stack.pop() // 2出栈 stack.pop() // 1出栈 复制代码
在一些简单的场景下,利用数组来模拟栈是可以满足条件的。但是作为一个功能完备的数据结构,还有一些其他的功能,使用上述的实现方式显的有点捉襟见肘。
那么,我们就自己实现一个比较功能完备的stack
。它有如下的功能点
push(element(s))
:添加一个(或几个)新元素到栈顶pop()
:移除栈顶的元素,同时返回被移除的元素peek()
: 返回栈顶的元素,不对栈做任何修改isEmpty()
:如果栈里没有任何元素就返回true
,否则返回false
size()
: 返回栈里的元素个数clear()
: 移除栈里所有的元素
class Stack { constructor() { this.items = []; } // 添加element到栈顶 push(element) { this.items.push(element); } // 移除栈顶的元素,同时返回被移除的元素 pop() { return this.items.pop(); } // 返回栈顶的元素,不对栈做任何修改 peek() { return this.items[this.items.length - 1]; } // 如果栈里没有任何元素就返回`true`,否则返回`false` isEmpty() { return this.items.length === 0; } // 返回栈里的元素个数 size() { return this.items.length; } // 移除栈里所有的元素 clear() { this.items = []; } } 复制代码
虽然,我们实现了一个功能完备的stack
结构,但是仔细一看,其实就是对array
中push/pop
等api
进行了一次包装。但是,经过包装后,使得针对stack
结构的各种操作,变得更具有封装性,而不会产生很多样板代码。
1. 后缀表达式
题目描述:
后缀表达式是一种算术表达式,也叫逆波兰式(
RPN
),它的操作符在操作数的后面。要求输入一个用字符串数组表示的后缀表达式,请输出该后缀表达式的计算结果。
示例:后缀表达式
["2","1","3","*","+"]
对应的表达式是2 + 1 * 3
,因此输出的计算结果为5
分析
- 以
["2","1","3","*","+"]
为例子分析。
- 从左往右扫描数组,首先遇到的操作数
2
,由于后缀表达式的特点,操作符还在后面,在操作符未知的情况下,是无法进行计算处理。所以,需要将当前的操作数进行暂存处理。 - 继续扫描数组,接下来的两个数据都是操作数,(
1/3
)还是没有操作符的出现,继续将对应的操作数进行暂存处理 - 继续扫描,直到遇到操作符(
*
)。按照后缀表达式的规则,此操作符对应的操作数是刚刚被暂存的一对操作数1/3
- 存储操作数的容器,是根据数据存入的时间顺序而排序。
1/3
明显位于容器的尾部。也就是说,需要从容器的尾部将一对数据取出,并做运算处理。 - 根据数据存入和取出的特点,我们可以利用
stack
来作为存储操作数的容器
- 一对操作数在操作符的作用下,合并成一个值,而这个值可能还会和未被处理的操作数进行计算,所以需要将其存入容器中
- 在容器中仅存唯一的数值,并且操作符也全部被消费了,此时容器中的数据就是后缀表达式最终的结果
代码实现
function evalRPN(tokens){ let stack = new Stack(); for(let token of tokens){ switch(token){ // 处理操作符 case "+": case "-": case "*": case "/": // 在源数据中,靠后的操作数 let back = stack.pop(); // 在源数据中,靠前的操作数 let prev = stack.pop(); // 计算操作数,并将其入栈处理 stack.push( calculate(prev,back,token) ); break; default: // 处理操作数,直接入栈 stack.push(parseInt(token)); } } // 操作符都处理完,且栈中只有一个数据 return stack.pop(); } 复制代码
辅助函数,用于处理两个操作数之间的算术问题。(有一点需要注意,就是操作数之间的顺序问题)
fucntion calculate(prev,back,operator){ switch(operator){ case "+": return prev + back; case "-": return prev - back; case "*": return prev * back; case "/": return (prev/back)>>0; // 数据取整 default: return 0; } } 复制代码
2. 小行星碰撞
输入一个表示小行星的数组
- 数组中每个数字的绝对值表示小行星的大小
- 数字的正负表示小行星运动的方向,正号表示向右飞行,负号表现向左飞行。
- 如果两个小行星相撞,体积小的小行星会消失,体积大的不受影响
- 如果相撞的小行星大小相等,两个都会消失
- 飞行方向相同的小行星永远不会相撞
示例:有6颗小行星[4,5,-6,4,8,-5]
,它们相撞之后最终剩下3颗小行星[-6,4,8]
分析
- 拿例子中的数据来分析,存在6颗小行星
[4,5,-6,4,8,-5]
- 第一颗是向右飞行大小为4的行星,此时不知道是否会和后面行星碰撞,先将其保存到某个数据容器中。(因为它位于第一位置,所以不需要考虑前面)
- 第二颗还是向右飞行大小为5的行星,它与现存且已知的行星方向相同,所以与其不会碰撞。但是,不知道是否与后面的行星是否发生碰撞,所以也是先将其存入到数据容器中。
- 第三颗是向左飞行大小为6的行星。由于它与现存且已知的行星方向相反,一定会相撞,大小为5的行星离它近,因此两个行星率先相遇。
- 由前面分析我们得知,我们先后往数据容器中依次存入了
4/5
,而在遇到方向不同的行星时,是率先取最近一次加入到数据容器的数据。也就是说,针对数据容器中的数据的存取,满足后进先出的规则。我们可以考虑用栈来具象化该数据结构。
- 在①中我们规定,针对向右飞行的行星,是采取了直接存入到数据容器中(
stack
)
- 如果当前元素是向左飞行时,此时就会发生碰撞,且他们直接遵循大值原则即谁大谁能存活。
- 并且向左飞行的元素秉持着,不撞南墙不回头的态度,只要栈里面还有额外的数据,它就要和stack中的数据
battle
一下,哪怕身败名裂 - 只有存活下来的元素,才配进入栈中
代码实现
function asteroidCollision(asteroids){ let stack = new Stack(); for(let as of asteroids){ // 当前元素向左飞行,并且该元素的绝对值比栈顶元素大 while(!stack.empty() && stack.peek()>0 && stack.peek()<-as ){ stack.pop(); } // 当前元素向左飞行,当前元素和栈顶元素体积一样 (需要互相抵消) if(stack.length && as<0 && stack.peek()==-as ){ stack.pop(); }else if( as >0 //当前元素向右飞行 || stack.empty() // 栈为空 (初始化) // 当前元素向左飞行(在经过对比后,还是无法消除) || stack.peek()<0 ){ stack.push(as) } } return stack; } 复制代码
上述的代码中,我们使用了Stack
中的一些方法。
3. 判断括号的正确性
给定一个只包括
'(',')'
,'{','}'
,'[',']'
的字符串 s ,判断字符串是否有效。 有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例:
输入:s = "()[]{}" 输出:true
输入:s = "(]" 输出:false
分析
- 当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合,但是,我们此时还用不到该左括号,所以,将其存入数据容器中
- 由于,题目中还需指定,必须以指定的顺序,此时,就需要考虑左括号的存入顺序了,后存入的先处理。即:后进先出的规则 ==> 那数据容器可以选为栈
代码实现
function isValid (s) { let stack = new Stack(); // 遍历 字符串 for(let c of s){ // 遇到左括号,将与其匹配的右括号入栈处理 if(c==='('){ stack.push(')') }else if(c==='['){ stack.push(']') }else if(c==='{'){ stack.push('}') // 遇到右括号 // 1. 判断栈内是否有括号,如果没有,那说明此时匹配不了 // 2. 满足①的情况下,判断此时字符是否和栈顶元素匹配 }else if(stack.length ===0 || stack.pop()!==c){ return false; } } // 最后再验证一下,栈是否为空,如果不为空,说明还有未匹配的括号 return !stack.length; }; 复制代码
3. 每日温度
输入一个数组,每个数字都是某天的温度。
计算每天需要等几天才会出现更高的温度
示例:输入数组
[35,31,33,36,34]
,输出结果为[3,1,1,0,0]
- 第一天温度为35°,要等3天才会出现更高的温度36°
- 第四天的文档是36°,后面没有更高的温度,与其对应的输出是0
分析
- 每次从数组中读出某一天的温度,并且都将其与之前的温度(保存在数据容器中的温度)相比较。
- 从离它较近的温度开始比较,也就是后存入数据容器中的温度先拿出来比较,满足后进先出的原则 ---> 我们选Stack作为数据容器
- 题目中,需要计算出现更高温度的等待天数,存入栈中的数据应该是温度在数组中的下标。
- 等待的天数就是两个温度在数组中的下标之差。
代码实现
function dailyTemperatures(temperatures){ // 定义一个与源数组相同的数组,用于存储最后结果 let result = new Array(temperatures.length); let stack = new Stack(); for(let i = 0;i<temperatures.length;i++){ // stack 非空,且当前的温度大于栈顶温度 while(!stack.empty() && temperatures[i]>temperatures[stack.peek()]){ // 取出,存于stack中的满足条件的温度的下标 let prev = stack.pop(); // 计算等待天数 并将其存入result[prev]中 result[prev] = i - prev; } // 将当前下标存入stack中 stack.push(i) } return result; } 复制代码
额外提醒
- 只有在 stack 非空,且当前的温度大于栈顶温度,才会从
stack
中取出栈顶元素 - 在满足条件的时候,是已经存入到
stack
中的数据,找到了它对应的需要等待的天数i - prev
直方图最大面积
输入一个由非负数组成的数组,数组中的数字是直方图中柱子的高,求直方图中最大矩形的面积
假设直方图中柱子的宽度为1
示例:输入数组
[2,1,5,6,2,3]
,直方图中最大矩形的面积为10(2*5)
分析 - 双指针法
- 如果直方图中一个矩形从下标为
i
的柱子开始,到下标为j
的柱子结束,那么两根柱子之间的矩形(含两端的柱子)的宽度是j-i+1
,矩形的高度就是两根柱子之间的所有柱子最矮的高度 - 如果能逐一找出直方图中所有矩形并比较它们的面积,就能得到最大的矩形面积
- 定义两个指针
i/j
:i
表示靠前的柱子下标,j
表示靠后的柱子下标
代码实现 - 双指针法
function largestRectangleArea(heights){ let maxArae = 0; for(let i=0;i<heights.length;i++){ let min = heights[i]; for(let j=i;j<heights.length;j++){ min = Math.min(min,heights[j]); let area = min * (j -i +1); maxArea = Math.max(maxArea,area) } } return maxArea; } 复制代码
想到maxX
是不是联想到选择排序 (最主要的特点就是找极值的序号(minIndex/largestIndex
))
我们来简单的再重温一下,选择排序的大体思路。
function selectionSort(arr){ let len = arr.length; if(len<2) return arr; // 处理边界值 let i,j,minIndex; // 外层循环: 控制迭代轮次 for(i=0;i<len-1;i++){ minIndex = i; // 内层循环:从内层循环中找到最小值的位置 for(j=i+1;j<len;j++){ // 在未排区域寻找最小的数,并记录其位置j if(arr[j]<arr[minIndex]) minIndex = j; } // 内层循环完毕,最小值确定,和已排区间最后一位交互位置 swap(arr,i,minIndex); } return arr; } 复制代码
这两个算法之间有很多相似的地方
- 双层循序
- 通过对极值的判断,对数据进行处理
由于采用了双层循环,所以该方法的时间复杂度为O(n²)
,不够优雅。我们可以采用更加优雅的处理方式。
分析 - 单调栈法
- 用一个栈来保存直方图的柱子,并且栈中的柱子的高度是递增排序的
- 为了方便计算矩形的宽度,栈中保存的柱子在数组中的下标
- 从左向右扫描数组中的每个柱子,
- 如果扫描到的柱子的高度大于位于栈顶的柱子的高度,那么将该柱子的下标入栈
- 如果扫描到的柱子的高度小于位于栈顶的柱子的高度,将位于栈顶的柱子的下标出栈,并且计算以位于栈顶的柱子为顶的最大矩形面积
- 由于保存在栈中的柱子的高度是递增排序的,栈中位于栈顶前面的一根柱子一定比位于栈顶的柱子矮
- 以某根柱子为顶的最大矩形,一定是从该柱子向两侧延伸直到遇到比它矮的柱子。
- 此时最大矩形的高就是该柱子的高
- 最大矩形的宽是两侧比它矮的柱子中间的间隔
代码实现-单调栈
function largestRectangleArea(heights){ let stack = new Stack(); stack.push(-1); let maxArea = 0; for(let i =0;i<heights.length;i++){ // 一边遍历,一边计算,当前高度,比栈顶高度小的数据 // 此时求的是以栈顶元素为高的面积 // 直到当前元素比栈顶元素都小时,才退出 while(stack.peek()!=-1 && heights[stack.peek()] >= heights[i]){ let height = heights[stack.pop()]; let width = i - stack.peek() -1; maxArea = Math.max(maxArea,height * width) } // 此时当前元素高度,比栈顶元素高,入栈处理 stack.push(i); } // 在处理完后,栈中还存在元素 // 这元素在后续的遍历中没找到比它矮的,所以,还需要进行相同操作 while(stack.peek()!=-1){ let height = heights[stack.pop()]; let width = heights.length - stack.peek() -1; maxArea = Math.max(maxArea,height * width) } return maxArea; } 复制代码
后记
分享是一种态度。
参考资料:剑指offer/leetcode官网
全文完,既然看到这里了,如果觉得不错,随手点个赞和“在看”吧。