Python3求栈最小元素

「爱情、让人受尽委屈。」 2022-04-10 12:28 155阅读 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 条评论，155人围观）

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

相关阅读

相关获取栈中最小元素

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

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

相关 leetcode 155：最小栈(python)

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

旧城等待，/ 2023年10月10日 08:24/ 0 赞/ 18 阅读

相关最小栈

1，原文 [https://leetcode-cn.com/problems/min-stack/][https_leetcode-cn.com_problems_min-s

ゝ一世哀愁。/ 2023年05月22日 14:25/ 0 赞/ 33 阅读

相关最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈（力扣题） push(x) —— 将元素 x 推入栈中。 pop() —— 删

Love The Way You Lie/ 2023年03月02日 04:59/ 0 赞/ 15 阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关 Python3求栈最小元素

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

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

相关最小栈

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

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