Python3求栈最小元素

「爱情、让人受尽委屈。」 2022-04-10 12:28 114阅读 0赞

\[本文出自天外归云的博客园\]

思路：入栈时靠辅助栈记住主栈元素中最小的，出栈时一直pop主栈元素直到辅助栈栈顶元素出现。

代码如下（定义栈、超级栈）：

class Stack(object):
        def __init__(self):
            self.items = []
    
        def push(self, ele):
            self.items.append(ele)
    
        def peek(self):
            return self.items[-1]
    
        def pop(self):
            top = self.items.pop()
            return top
    
    
    class SuperStack(Stack):
        def __init__(self):
            self.stack = Stack()
            self.temp = Stack()
    
        # 入栈的时候把最小的元素放到辅助栈栈顶
        def push(self, ele):
            if self.temp.items == []:
                self.temp.push(ele)
            elif ele < self.temp.peek():
                self.temp.push(ele)
            self.stack.push(ele)
    
        # 出栈的时候一直pop直到等于辅助栈栈顶元素的元素出现
        def pop(self):
            min = self.temp.peek()
            while True:
                if self.stack.peek() != min:
                    print(f'POP:{self.stack.pop()}')
                else:
                    print(f'MIN:{self.stack.peek()}')
                    break
    
    
    if __name__ == '__main__':
        ss = SuperStack()
        ss.push(22)
        ss.push(3)
        ss.push(33)
        ss.push(4)
        ss.push(55)
        ss.push(12)
        ss.push(13)
        ss.push(16)
        ss.pop()

运行结果：

![714263-20180518155440185-1409439066.png][]

[714263-20180518155440185-1409439066.png]: /images/20220330/0ea939dd0ef04ac99f87dd700b08162e.png

发表评论取消回复

表情：

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

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

相关阅读

相关获取栈中最小元素

public class MinStack { private Stack<Integer> mainStack = new Stack<Integ...

﹏ヽ暗。殇╰゛Y/ 2024年04月20日 08:43/ 0 赞/ 34 阅读

相关 python求最大公约数和最小公倍数

法1 a=24 b=36 a的约数集(第1种求法) setys_a=set() for i in range(1,a+1):

缺乏、安全感/ 2024年02月18日 23:48/ 0 赞/ 17 阅读

相关 LeetCode题目（Python实现）：最小栈

文章目录题目想法一：辅助栈算法实现执行结果复杂度分析小结

小咪咪/ 2023年07月16日 11:58/ 0 赞/ 53 阅读

相关返回栈内最小元素（辅助最小值栈）

返回栈内最小元素 class Solution1: def __init__(self): self.stack = [

淩亂°似流年/ 2022年12月31日 01:17/ 0 赞/ 104 阅读

相关 js 求一个数组元素的最小公倍数

今天我在网上查 “js 求一个数组元素的最小公倍数”，不管是Google还是百度，查出来的答案竟然都是一样的，最关键的是这是错误的。错误在哪那！刚一看感觉是正确的，而且你输

男娘i/ 2022年08月08日 06:20/ 0 赞/ 133 阅读

相关构造一个特殊栈，实现方法getmin，返回栈中的最小元素 Python版

题目：构造一个栈结构，其中需要实现一个方法，该方法 getmin，返回栈中的最小的元素。要求：时间复杂度为o（1）。分析：之前我写过了用python写

浅浅的花香味﹌/ 2022年06月03日 08:14/ 0 赞/ 123 阅读

相关选择问题（求第k个最小元素）

什么是选择问题划分的思路 Lomuto 划分利用划分求第k小元素 C语言实现改进参考资料什么是选择问题选择问题（s

喜欢ヅ旅行/ 2022年05月24日 12:44/ 0 赞/ 120 阅读

相关 Python3求栈最小元素

\[本文出自天外归云的博客园\] 思路：入栈时靠辅助栈记住主栈元素中最小的，出栈时一直pop主栈元素直到辅助栈栈顶元素出现。代码如下（定义栈、超级栈）： cla

「爱情、让人受尽委屈。」/ 2022年04月10日 12:28/ 0 赞/ 115 阅读

相关最小栈

题目描述设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素

古城微笑少年丶/ 2022年02月25日 00:28/ 0 赞/ 213 阅读

相关求最大公约数和最小公倍数_python

"""写两个函数，分别求两个整数的最大公约数和最小公倍数，调用这两个函数，并输出结果。两个整数由键盘输入。""" ''' 设两个整数u和v，用辗转相除法

你的名字/ 2021年09月30日 00:52/ 0 赞/ 325 阅读