剑指 Offer 30. 包含min函数的栈(python3编写)
2022/1/28 17:04:41
本文主要是介绍剑指 Offer 30. 包含min函数的栈(python3编写),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
- 1、题目描述:
- 2、方法:
- 思路:
- 代码:
1、题目描述:
2、方法:
思路:
思路来源:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/
普通栈的 p u s h ( ) push() push() 和 p o p ( ) pop() pop() 函数的复杂度为 O ( 1 ) O(1) O(1) ,而获取栈最小值 m i n ( ) min() min() 函数需要遍历整个栈,复杂度为 O ( N ) O(N) O(N)。
本题难点在于: 将 min() 函数复杂度降为 O ( 1 ) O(1) O(1) ,可通过建立辅助栈实现。细节下面一一说来:
数据栈 A A A : 栈 A A A 用于存储所有元素,保证入栈 p u s h ( ) push() push() 函数、出栈 p o p ( ) pop() pop() 函数、获取栈顶 t o p ( ) top() top() 函数的正常逻辑。
辅助栈 B B B : 栈 B B B 中存储栈 A A A 中所有 非严格降序 的元素,则栈 A A A 中的最小元素始终对应栈 B B B 的栈顶元素,即 m i n ( ) min() min() 函数只需返回栈 B B B 的栈顶元素即可。
因此,只需设法维护好 栈 B B B 的元素,使其保持非严格降序,即可实现 m i n ( ) min() min() 函数的 O ( 1 ) O(1) O(1) 复杂度。如下图所示:
如果还有点懵逼,下面我说一下具体的做法就知道怎么回事了:
- 当元素入栈时,即执行 p u s h ( ) push() push()函数时,我们将元素压入数据栈 A A A中,同时检查当前辅助栈 B B B的情况:辅助栈 B B B为空或者当前要 p u s h ( ) push() push()的元素小于等于辅助栈 B B B栈顶的元素,则把当前元素也压入辅助栈 B B B。
- 当元素出栈时,我们把数据栈 A A A栈顶的元素弹出,同时检查数据栈 A A A栈顶元素是不是等于辅助栈 B B B栈顶元素,如果等于,则把辅助栈 B B B栈顶元素也出栈。
代码:
class MinStack: def __init__(self): """ initialize your data structure here. """ self.stackA = [] # 数据栈 self.stackB = [] # 辅助栈 def push(self, x: int) -> None: self.stackA.append(x) if not self.stackB or self.stackB[-1] >= x: self.stackB.append(x) # 如果stackB为空,或者x小于等于栈顶元素,则x直接入stackB def pop(self) -> None: # 栈B中存储栈A中所有非严格降序的元素,则栈A中的最小元素始终对应栈B的栈顶元素 if self.stackA.pop() == self.stackB[-1]: self.stackB.pop() def top(self) -> int: return self.stackA[-1] # 栈顶元素 def min(self) -> int: return self.stackB[-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.min()
这篇关于剑指 Offer 30. 包含min函数的栈(python3编写)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-18初探Python股票自动化交易:入门指南
- 2024-09-18Python量化入门:轻松掌握量化分析基础与实战
- 2024-09-18Python量化交易:入门指南与实践
- 2024-09-18Python量化交易:入门指南与实战技巧
- 2024-09-14Python人工智能项目实战:从零开始的实践指南
- 2024-09-14探索Python人工智能资料:初学者的指南
- 2024-09-14Python人工智能资料:初学者的全面指南
- 2024-09-13Matplotlib入门:轻松绘制Python数据可视化图表
- 2024-09-13Python人工智能:初学者的入门指南
- 2024-09-13Python人工智能:轻松入门与实践