最小栈的实现

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

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

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

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目:实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个方法。要保证这三个方法的时间...
    Caolongs阅读 240评论 0 0
  • Lua 5.1 参考手册 by Roberto Ierusalimschy, Luiz Henrique de F...
    苏黎九歌阅读 13,889评论 0 38
  • 先来个简单的栈(先进后出) 题目:实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个...
    darklindj阅读 1,347评论 0 0
  • 为了补考科目三,今天下午去练车了。带我的教练请假了,所以由另外一个教练带我们练.一直以来都以为是自己眼睛有点斜视,...
    玲夏ling阅读 214评论 0 0
  • 这个世界上,有一个人是永远等着你的。不管什么时候,不管什么地方。反正,总有这么个人。这句话,让我找得很是辛苦。《表...
    飘雨桐V阅读 236评论 0 0