题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
在读题时，最开始没get到点，认为不就是在一个数组的pop()和append()的基础上，增添一个寻找数组中最小值的函数嘛，后来很快意识到这个肯定不是最佳答案，因为每min()一次，就要遍历一次数组，不合理。因此就要思考如何保存堆栈中的min值，尤其是当push()或pop()后，堆栈中状态发生变化时，如何同步保存其中的最小值呢，也可以理解为如何同步保存堆栈中的某一特征（不一定是min）。后来才想到可以建一个辅助栈，与正式stack同步pop或push，只不过辅助栈中存储的是min值（或其它需要保存的特征值），这样即可实现用空间换时间，同步保存堆栈的某特征值。（真是个猪猪，脑子不会转弯）
后来还想到，可以利用二维数组（或多维数组，字典）来同步保存状态值。不过，只有在堆栈、链表、队列这类会实时发生变化的数据结构中，才存在如何同步保存数据结构状态的问题。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, node):
min_node = self.min()
if min_node == None:
min_node = node
if min_node < node:
self.min_stack.append(min_node)
else:
self.min_stack.append(node)
self.stack.append(node) #min_stack与stack同步push
def pop(self):
if self.stack:
self.min_stack.pop()
return self.stack.pop()#min_stack与stack同步pop
else:
return
def top(self):
if self.stack:
return self.stack[-1]
else:
return
def min(self):
if self.stack:
return self.min_stack[-1]
else:
return
网友评论