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