【剑指offer】包含min函数的栈【python】

以你之姓@ 2022-04-17 00:19 153阅读 0赞

**题目描述**  
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。  
算法思想，采用一个辅助栈的形式。

1.  如果push了一个比较大的数字，那么仍然在辅助栈中push最小值，这样pop之后这个大数字之前或者之后，辅助栈顶仍然是栈中的全局最小
2.  如果push了一个比较小的数字，那么将这个小数字push到辅助栈中，这样辅助栈的top仍然是最小，pop这个小数字之后，辅助栈仍然维护到了全局最小的数字  
    需要注意的是：当辅助栈没有数字的时候，直接push，不需要比较，这里需要考虑代码的完整性

--------------------

class Solution:
        def __init__(self):
            self.stack = []
            self.minStack = []
        def push(self, node):
            # write code here
            self.stack.append(node)
            if self.minStack == []:
                self.minStack.append(node)
            else:
                min = self.minStack[len(self.minStack) - 1]
                if node <= min:
                    self.minStack.append(node)
                else:
                    self.minStack.append(min)
        def pop(self):
            self.stack.pop()
            self.minStack.pop()
        def top(self):
            # write code here
            return self.stack[len(self.stack) - 1]
        def min(self):
            # write code here
            return self.minStack[len(self.minStack) - 1]

发表评论取消回复

表情：

评论列表（有 0 条评论，153人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指Offer：包含min函数的栈（Python）

题目定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数。时间复杂度应为O（1）思路空间换时间另一个栈一直存储最小值解答

约定不等于承诺〃/ 2023年07月17日 06:30/ 0 赞/ 77 阅读

相关剑指offer——包含min函数的栈

题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。分析：定义一个辅助栈，保存对应元素存在时当前栈中的最小元素，即可在O(1)的时间内找到最小的

叁歲伎倆/ 2022年05月31日 12:50/ 0 赞/ 177 阅读

相关剑指Offer-包含min函数的栈

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。基本思路：利用两个栈，一个数据栈，一个辅助栈（保存当前栈中数据的最小值）数据栈和辅

古城微笑少年丶/ 2022年05月23日 01:17/ 0 赞/ 167 阅读

相关【剑指offer】包含min函数的栈【python】

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。算法思想，采用一个辅助栈的形式。 1. 如果pus

以你之姓@/ 2022年04月17日 00:19/ 0 赞/ 154 阅读

相关剑指offer:包含min函数的栈

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 AC C++ Solution: 使用两个栈,一个栈

缺乏、安全感/ 2022年04月10日 07:58/ 0 赞/ 202 阅读

相关【剑指offer】包含min函数的栈

包含min函数的栈题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 AC代码思路：用一个

痛定思痛。/ 2022年04月02日 15:52/ 0 赞/ 175 阅读

相关剑指Offer-包含min函数的栈

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数 (时间复杂度应为O(1))。看到题目特别是模拟编辑器上的代码，给了四个空函数，一

「爱情、让人受尽委屈。」/ 2022年02月27日 11:56/ 0 赞/ 200 阅读

相关剑指Offer——包含min函数的栈

1、题目描述　　定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 2、代码实现 package com.b

梦里梦外;/ 2021年12月04日 05:07/ 0 赞/ 244 阅读

相关剑指offer 包含min函数的栈

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为

系统管理员/ 2021年11月02日 05:04/ 0 赞/ 301 阅读

相关剑指offer：包含min函数的栈

试题：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。代码：为了实现栈的功能，我们可以简单的利用java

ゞ浴缸里的玫瑰/ 2021年06月24日 16:09/ 0 赞/ 339 阅读