UDN-企业互联网技术人气社区

板块导航

浏览  : 1423
回复  : 0

[其它] 漫画算法:最小栈的实现

[复制链接]
泡泡兔的头像 楼主
发表于 2016-11-7 10:42:45 | 显示全部楼层 |阅读模式
1.jpg

2.jpg

3.jpg

4.jpg

5.jpg

6.jpg

7.jpg

8.jpg

9.jpg

10.jpg

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

12.jpg

  小灰的想法:

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

  2.当第一个元素进栈时,让min=0,即把唯一的元素当做最小值。

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

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

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

2.jpg

3.jpg

4.jpg

  回忆到此结束……
1.jpg

2.jpg

3.jpg

4.jpg

5.jpg

6.jpg

7.jpg

  解法:

  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对应元素即可。

相关帖子

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部