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