压缩还原,大佬思路的Python实现

包含min函数的栈

http://www.nowcoder.com/questionTerminal/4c776177d2c04c2494f2555c9fcc1e49

这题有两种解法
一、借助辅助栈,保存一系列的最小值
当有比当前最小值还小的元素进来,压进辅助栈,当执行pop()操作则要对比栈与辅助栈的元素大小,判断辅助栈是否需要同样执行pop()操作
二、压缩还原
栈保存该元素与最小值的差值,更新最小值

class Solution:
    def __init__(self):
        self.stack = []
        self.min_num = 0
    def push(self, node):
        if not self.stack:
            self.stack.append(0)
            self.min_num = node
        else:
            self.stack.append(node - self.min_num)
            if self.min_num > node:
                self.min_num = node
    def pop(self):
        # write code here
        if self.stack:
            temp = self.stack.pop()
            if temp >= 0:
                return self.min_num + temp
            else:
                self.min_num = self.min_num - temp
                return self.min_num + temp
    def top(self):
        if self.stack:
            temp = self.stack[-1]
            if temp >= 0:
                return self.min_num + temp
            else:
                return self.min_num
    def min(self):
        return self.min_num
全部评论

相关推荐

钱嘛数字而已:辅导员肯定不能同意,不然你出事了,他要承担责任。但是,脚和脑子都长在你自己身上,使用它还需要向辅导员报告么? 辅导员必须按流程拒绝你,然后你拿出成年人的态度,做自己的选择。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务