设为首页 - 加入收藏
您的当前位置:IT独行侠新闻社 > IT漫画 > 正文

IT独行侠:漫画算法最小栈的实现

来源:网络整理 编辑:IT独行侠 时间:2017-06-13

来自:梦见(微信号:dreamsee321)

已获转载授权


IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

小灰回忆起当时的情景……

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

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

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

小灰的想法:

1.创建一个整型变量 min,初始值-1

2.当第一个元素进栈时,让min=0,IT独行侠新闻社,即把唯一的元素当做最小值。

3.之后每当一个新元素近栈,让新元素和min指向位置的元素比较大小。如果Stack[min]大于新元素,则min等于新元素的下标;Stack[min]小于新元素,则不做改变。

4.当调用getMin方法的时候,直接返回min所指向位置的元素即可。

IT独行侠:漫画算法最小栈的实现

按这个思路,近栈、出栈、取最小值的时间复杂度都是O(1),空间复杂度也是O(1)。

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

回忆到此结束……

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

IT独行侠:漫画算法最小栈的实现

解法:

1.设原有的栈叫做栈A,此时创建一个额外的栈B,用于辅助原栈A。

2.当第一个元素进入栈A的时候,让新元素的下标进入栈B。这个唯一的元素是栈A的当前最小值。(考虑到栈中元素可能不是类对象,所以B栈存储的是A栈元素的下标)

3.每当新元素进入栈A时,比较新元素和栈A当前最小值的大小,如果小于栈A当前最小值,则让新元素的下标进入栈B,此时栈B的栈顶元素就是栈A当前最小值的下标。

4.每当栈A有元素出栈时,如果出栈元素是栈A当前最小值,则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的,是栈A当中原本第二小的元素,代替刚才的出栈元素成为了栈A的当前最小值。(备胎转正)

5.当调用getMin方法的时候,直接返回栈B的栈顶所指向的栈A对应元素即可。

IT独行侠:漫画算法最小栈的实现

这个解法中近栈、出栈、取最小值的时间复杂度都是O(1),最坏情况空间复杂度是O(N)。

IT独行侠:漫画算法最小栈的实现

扩展题目:

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

IT独行侠:漫画算法最小栈的实现


来自:梦见(微信号:dreamsee321)

IT独行侠:漫画算法最小栈的实现

网友评论:

无法在这个位置找到: ajaxfeedback.htm

猜你喜欢

本网站部分文章采集于网络、报纸、杂志等其它媒体,如侵犯了原作者的版权,请来信告知,本站将立即删除

Copyright ©2017 www.itxws.com IT独行侠新闻社 让IT独行的路上不再孤单

Top