扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
创新互联公司从2013年开始，先为上蔡等服务建站，上蔡等地企业，进行企业商务咨询服务。为上蔡企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
class Solution:
"""
由于需要包含min函数且满足栈的性质，那么我们可以增加一个保存辅助栈来保存最小值。
假设我们设计两个存储栈，一个叫数据栈，一个叫最小栈。
当数据栈有压入操作的时候，最小栈也执行一个压入操作，但是压入的值是当前数据栈中的最小值；
当数据栈有弹出操作的时候，最小栈也执行一个一样的常规弹出操作
"""
def __init__(self):
self.min_stack = []
self.data_stack = []
def push(self, node):
# 入栈的时候只需要压入当前数据栈中的最小值，
# 那么当出栈的时候如果数据栈弹出的是最小值，那么最小栈也弹出了最小值
# 如果数据栈弹出的不是最小值，那么最小栈弹出之后全局最小值还保留在栈中。
# 通过这样设计，最小栈的栈顶永远保存着全局的最小值，这样我们就可以通过min函数获取最小值
self.data_stack.append(node)
self.min_stack.append(min(self.min_stack[-1], node)
if self.min_stack else node)
def pop(self):
if self.data_stack:
self.data_stack.pop(-1)
self.min_stack.pop(-1)
def top(self):
if self.data_stack:
return self.data_stack[-1]
def min(self):
if self.min_stack:
return self.min_stack[-1]
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网