压缩还原,大佬思路的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
全部评论

相关推荐

小谷围鸡肉卷阿姨:+1,腾子投完一动不动
点赞 评论 收藏
分享
勇敢的联想人前程似锦:如果我是你,身体素质好我会去参军,然后走士兵计划考研211只需要200多分。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务