LeetCode如何实现包含min函数的栈
这篇文章给大家分享的是有关LeetCode如何实现包含min函数的栈的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
创新互联专注于点军网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供点军营销型网站建设,点军网站制作、点军网页设计、点军网站官网定制、微信平台小程序开发服务,打造点军网络公司原创品牌,更为您提供点军网站排名全网营销落地服务。
题目描述
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
各函数的调用总次数不超过 20000 次
题目样例
示例
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
题目思考
内部需要什么数据结构来满足所有操作都是 O(1), 一个栈够吗?
解决方案
思路
要使得 push 和 pop 的复杂度为 O(1), 传统的栈就可以搞定, 难点在于如何使得 min 函数也为 O(1) 如果我们能一直维护当前所有元素的最小值, 那么 min 函数直接返回它就可以, 但问题是在 pop 的时候有可能会正好 pop 这个最小值, pop 之后的最小值(也即原来的次小值)如何得到呢? 要存储多个最小值, 显然一个变量不够用. 而根据上一步的分析, 这里我们可以考虑额外引入一个 单调递减栈, 栈顶存当前最小值, 下面依次是次小, 第三小... 这样如果 pop 了最小值的话, 这个单调栈的栈顶仍会保存 pop 后的最小值, 每次 min 只需要取这个栈的栈顶即可 而 push 的时候也需要额外的操作, 由于是单调栈, 只需要在新的值 小于等于栈顶的时候才 push 到单调栈中.特别注意在等于栈顶的时候也要 push 到单调栈中, 这是因为如果对于重复的最小值 x 不 push, 那么在后续的 pop 其中一个 x 之后, 栈顶(不再是 x)就和实际最小值(仍为 x)不一致了
复杂度
时间复杂度 O(1)
各种操作都是常数复杂度 空间复杂度 O(N)
使用了两个栈
代码
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
# 一个普通栈和一个单调递减栈
self.minstack = []
self.stack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.minstack or x <= self.minstack[-1]:
# 如果单调栈顶为空或者当前新值小于等于单调栈顶才push
# 注意这里等于也需要push. 如果对于重复的最小值 x 不 push, 那么在后续的 pop 其中一个 x 之后, 栈顶(不再是 x)就和实际最小值(仍为 x)不一致了
self.minstack.append(x)
def pop(self) -> None:
if not self.stack:
return
x = self.stack.pop()
if x == self.minstack[-1]:
# 如果单调栈顶恰好等于pop的值, 也要pop单调栈
self.minstack.pop()
def top(self) -> int:
if not self.stack:
return -1
return self.stack[-1]
def min(self) -> int:
if not self.minstack:
return -1
return self.minstack[-1]
感谢各位的阅读!关于“LeetCode如何实现包含min函数的栈”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
分享标题:LeetCode如何实现包含min函数的栈
文章起源:http://pwwzsj.com/article/pcgdpc.html