LeetCode155 最小栈

  • 作者:zyh
  • 分类:LeetCode
  • 发表日期:2020-07-03 12:29:44
  • 阅读(290)
  • 评论(0)

LeetCode第155题,最小栈。

题目描述的要求是,设计一个支持push、pop、top操作,并且能在常数时间内检索到的最小元素的栈。

所谓常数时间就是要求时间复杂度要为O(1)

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

现在来思考如何解决这道题,难点在于要用O(1)时间复杂度来取出最小值。栈的特点是后进先出,就是最后一个入栈的元素一定是最先被弹出的。所以如果这道题是按照从大到小的元素入栈倒还好说,每次出栈肯定是最小的元素,并且还是时间复杂度也是O(1),但要是无序的呢?

此时一个栈肯定是满足不了上述条件的,可以考虑定义两个栈,一个用来正常存储元素stack,另一个用来存储最小的元素min_stack,但是要注意,当第一次放入元素的时候,这两个栈肯定都是空栈,所以第一次存放的元素这两个栈都要存储。第二次存放元素的时候,stack正常存储值,此时min_stack就要进行判断,如果这个要存入栈的元素比栈顶元素小,那就让它入栈,否则就不让入栈,一定要保证min_stack里栈顶元素一定是最小值。

既然入栈已经整理好了,接下来说说出栈,出栈的时候,要判断stack即将弹出的元素是否等于min_stack的栈顶元素的值,如果是,那顺便将min_stack的元素也一块弹出,如果不相等就只把stack的元素弹出就好。这样就保证了min_stack栈顶元素始终是最小值。

代码如下:

LeetCode155 最小栈

提交评论

您尚未登录 :-( ,登录之后方可评论 登录 or 注册

评论列表

暂无评论