这篇文章给大家分享的是有关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)不一致了
复杂度
代码
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://www.cdkjz.cn/article/pcgdpc.html
