最小栈和最小队列

编者按:本文作者高峰,360奇舞团前端工程师,W3C性能工作组/WOT工作组成员。

相信栈和队列这两种数据结构大家一定都不陌生吧。这两种数据结构有个特殊形式:即最小栈和最小队列。

下面我们分别来介绍下这两个带有“特异功能”的数据结构。

一、最小栈

1. 什么是最小栈

实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个方法。并且这三个方法的时间复杂度都是O(1)。

2. 设计思路

2.1 错误思路

看了上面对于最小栈的定义后,可能大部分人都能够快速想到这样的思路:

创建一个栈,再额外声明一个变量,用于存储栈的最小值。将第一个入栈的元素赋值给最小值变量。之后在每次进行入栈操作时,判断最小值变量与新入栈元素的大小。如果新入栈元素小于最小值变量,则修改最小值变量的值为新入栈元素。

这样我们就实现了一个栈,并且还会有一个变量指向栈的最小值。

不过遗憾的是,这个思路是错误的。因为当我们进行出栈操作的时候,如果最小值出栈了,那所声明的最小值变量就没有意义了。

所以我们在最小值出栈的时候,需要有更换顶替当前最小值的次最小值。

2.2 正确思路

上面说了,我们在最小值出栈时,需要有更换顶替当前最小值的值。我们可以通过两个栈来实现,第一个栈用于存放入栈的元素,第二个栈用于存放最小元素。

具体思路如下:

  1. 创建两个栈分别为A和B,A用于存放入栈的元素,B用于存放最小值在A中的下标或索引。

  2. 当第一个元素入A栈时,同时将其索引值推入B栈。

  3. 之后每个元素入栈A栈时,都将其与B栈栈顶的索引值对应的元素值比较,如果 大于等于 该元素,则忽略,如果小于该元素则入栈B。

  4. 这时,B栈的栈顶元素即为栈A的最小元素的索引。

  5. 每次元素出A栈时,如果出栈的元素的索引值等于B栈的栈顶元素,则将B栈的栈顶元素也出栈。出栈后,B栈顶的元素就会顶替出栈的最小值。

注意:B栈中之所以存索引,是因为这样可以规避一些问题。如当后加入的值和最小值相同时,如果我们不重复入栈B,那么出栈的时候对于B栈的判断就可能出问题(后入的等值元素可能会导致最小值提前出栈)。存索引就可以避免重复入栈最小值这个问题,节省一定的空间。

3. 算法实现

为了便于展示,笔者使用Vue实现了这一算法。详情可以参见https://jsbin.com/lokedoxere。实现效果如下图:

算法逻辑如下:

// 下述代码使用Vue实现,只是其中的部分

data : function ( ) {

return {

// ...

minIndeices : [ ] ,

stack : [ ] ,

}

} ,

methods : {

// 获取最小值

getMin : function ( ) {

const lastMinIndex  = this . minIndeices [ this . minIndeices . length  - 1 ]

return this . stack [ lastMinIndex ]

} ,

// 出栈

pop : function ( ) {

const len  = this . stack . length

if ( len  === 0 ) return

const lastMinIndex  = this . minIndeices [ this . minIndeices . length  - 1 ]

// 如果栈顶的最小值索引等于原始栈的长度 - 1,

// 即出栈的元素为最小值,则最小值索引栈也出栈

if ( lastMinIndex  === len  - 1 ) {

this . minIndeices . pop ( )

}

this . stack . pop ( )

} ,

// 入栈

push : function ( ) {

if ( this . number  === undefined ) return

const len  = this . stack . length

// 如果栈为空,即添加的元素为第一个,存入第一个最小值索引

if ( len  === 0 ) {

this . minIndeices . push ( len )

} else {

const currMin  = this . getMin ( )

if ( this . number  < currMin ) {

this . minIndeices . push ( len )

}

}

this . stack . push ( this . number )

this . number  = undefined

} ,

}

至此,我们实现了最小栈的逻辑。其实最小队列的实现思路与最小栈类似。不过又略有点不同。下面我们一起来看看吧。

二、最小队列的实现

1. 什么是最小队列

实现一个队列,带有出队(deQueue),入队(enQueue),取最小元素(getMin)三个方法。要保证这三个方法的时间复杂度都 尽可能小

2. 设计思路

这里我就不卖关子了,直接进入正题。

我们可以通过两个队列实现,第一个队列用于存放入队的元素,第二个队列用于存放最小值。

详细思路如下:

  1. 创建两个队列分别为A和B,A用于存放入队的元素,B用于存放最小值(严格来说,B不能称作队列,它会将后入的元素删除)。

  2. 当第一个元素入队A时,同时将其入队B,因为这是就唯一一个值,所以是最小值。

  3. 之后每个元素入队A时,从B队尾开始比较,如果当前值大于等于(要有等于)B队尾值,则入队;否则,则删除B队尾值;然后再次比对B队尾值和当前值大小,直到当前值大于等于(要有等于) B队尾值或B为空,则当前值入队B尾。

  4. 这时每次B队中队首元素即为最小值。

  5. 当A中的元素出队时,如果元素值刚好与B队首元素相等,则B队首的元素也出队。(第三步中包含等于的判断,就是为了避免出队时等值元素不会出问题。)

  6. 这时deQueue/getMin时间复杂度为O(1)。enQueue为O(n)。

注意:不能像最小栈那样存索引,因为队列中的值的索引会变。所以重复的最小值要多次加入B。

3. 算法实现

同样,笔者使用Vue实现了这一算法。详情可以参见https://jsbin.com/genigakudu。实现效果如下图:

算法逻辑如下:

data: function () {

return {

// ...

minQueue : [ ] ,

queue : [ ] ,

}

} ,

methods : {

// 获取最小值

getMin : function ( ) {

return this . minQueue [ 0 ]

} ,

// 出队

deQueue : function ( ) {

const deNum  = this . queue . shift ( )

if ( deNum  === this . minQueue [ 0 ] ) this . minQueue . shift ( )

} ,

// 入队

enQueue : function ( ) {

if ( this . number  === undefined ) return

const len  = this . queue . length

// 如果队列为空,即添加的元素为第一个,存入第一个最小值

if ( len  === 0 ) {

this . minQueue . push ( this . number )

} else {

this . minQueue  = this . minQueue . filter ( item  = > item  <= this . number )

this . minQueue . push ( this . number )

}

this . queue . push ( this . number )

this . number  = undefined

} ,

}

引申

上面我们介绍并实现了最小栈和最小队列,其实大家也可以用类似的方法实现出最大栈和最大队列。如果大家有兴趣就自己动手试试吧。

关于奇舞周刊

《奇舞周刊》是360公司专业前端团队「 奇舞团 」运营的前端技术社区。关注公众号后,直接发送链接到后台即可给我们投稿。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章