漫画算法:最小栈的实现

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%841

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%842

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%843

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%844

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%845

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%847

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

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%951

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%952

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%953

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%954

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%955

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

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%956

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%957

小灰的想法:

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

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

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

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

%e6%9c%80%e5%b0%8f%e6%a0%88%e7%9a%84%e5%ae%9e%e7%8e%b01

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

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%958

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%959

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9510

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%a4%b1%e6%9c%9b

回忆到此结束……

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%848

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%849

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8410

%e6%9c%80%e5%b0%8f%e6%a0%88%e7%9a%84%e5%ae%9e%e7%8e%b02

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8411

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8412

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8413

解法:

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

%e6%9c%80%e5%b0%8f%e6%a0%88%e7%9a%84%e5%ae%9e%e7%8e%b03

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

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8414

扩展题目:

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

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8415

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

3 14 收藏 29 评论

关于作者:玻璃猫

互联网公司的码农一枚,喜欢算法和面向对象设计。个人微信号:13522239721 个人订阅号:dreamsee321欢迎一起交流讨论! 个人主页 · 我的文章 · 70 ·  

相关文章

可能感兴趣的话题



直接登录
最新评论
  • DeepKolos 大二,前端菜鸟 10/24

    pop似乎不会更新栈B,那么如果pop那个正是下一个min项,那么下次getmini是不是会出错?

    • 南山一叶 软件攻城狮 10/24

      "4.每当栈A有元素出栈时,如果出栈元素是栈A当前最小值,则让栈B的栈顶元素也出栈。"

      会更新栈B的

    • 玻璃猫 程序员 10/24

      可以看下步骤四所说的:

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

      • DeepKolos 大二,前端菜鸟 10/24

        如果Pop不是栈A的最小值?是直接出栈吗?栈B又如何更新?

        那么两个或者多个相同最小值的情况如何处理?

        还有栈A和栈B是不对称的,那么我想通过getmin全部导出栈A,好像不行吧

        • 南山一叶 软件攻城狮 10/24

          1.不是栈A的最小值直接出栈,栈B不更新

          2.有多个相同最小值时都入到栈B里。出栈的时候如果为当前最小值,栈A和栈B同时出栈

          3.是不行

  • 南山一叶 软件攻城狮 10/24

    扩展题目:

    维护一个队列A和一个数组B。

    每次有元素x入队列时,从头扫描数组B,如果元素x小于数组B该位置的值,则更新该位置的值为x,然后再把元素x加入队列A和数组B的末尾。

    有元素出队列时,删除数据B对应位置的元素。

    数组B的起始位置则为队列的最小元素。

    入队列和出队列的时间复杂度是O(N),取最小元素的时间复杂度为O(1)。

    暂时没想到其他更好的办法了...

  • 王念一 初三学生 10/24

    令最小队列三个算法都是O(1)是不可能的,别试了

    要不出入队列是O(logN)(即维护一个堆),要不求最小是O(N)(用两个栈模拟一个队列)

  • ★小V★ 程序員 10/24

    如果是這種方法呢?

    把他當做一個linked list來看的話...每一個數都是一個Node,而這個Node包括了自己的值,這個值當時進去的時候的最小數,然後一個指針指下一個,應該是可以保證push, pop還有getMin是O(1)....

    我是參考了這個的http://www.programcreek.com/2014/02/leetcode-min-stack-java/

  • 小C   10/25

    为什么要再添一个栈呢,只要栈数据结构中添加一个当前最小元素即可嘛。即类似 于这样 :

     

  • 小C   10/25

    为什么要再添一个栈呢,只要栈数据结构中添加一个当前最小元素即可嘛。即类似 于这样 :

     

  • 小小程序猿   10/25

    已打赏,加油!!

  • 用arr[2n]存储元素,start和end记录队列的首尾,min[n]记录最小备胎。

    出队和min是O(1),入队一般情况下是O(1)达到边界时会触发arraycopy和min[]的重新赋值,此时为O(N),但如果考虑平摊的话,也可以认为综合情况是O(1),

  • 已打赏~PS:在51nod群的昵称记得也是玻璃猫啊~是改了么还是退出了?找不到你人了~

  • 宅男阿莱格里 伪·LL教徒 10/25

    跟小灰一样Naive and simple_(´ཀ`」 ∠)_

    顺便谢谢大家的分享XD

  • HaopengWang   10/28

    扩展问题可以实现入队O(logN),出队和最小值O(1)。

    入队操作:维护一个最大值为最近入队的值的单调递增队列,递增队列的值的顺序与数据队列里的顺序一致。每次入队时用二分查找找到递增队列里小于入队值的最大值,递增队列里大于这个值的全部舍弃,然后将入队值入队递增队列。

    出队操作类似最小栈,当前最小值就是递增队列第一个值。

    • 出队列的时候,辅助队列的变化是On的吧?

      • HaopengWang   11/10

        出队时只需查看出队值是不是辅助队列的第一个值(如果有重复值可以比较下标),不是的话不用处理辅助队列,是的话辅助队列出队操作。

跳到底部
返回顶部