资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

剑指offer:包含min函数的栈

题目描述
定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的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]

本文标题:剑指offer:包含min函数的栈
URL标题:http://www.cdkjz.cn/article/gccjoo.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220