本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 Unported许可协议进行许可。允许非商业转载，但应注明作者及出处。
作者：liuyuan_jq
2011-07-13
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
该思路存在一个重要的问题：如果当前最小元素被pop出去，如何才能得到下一个最小元素？
因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。我们需要一个辅助栈。每次push一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；每次pop一个元素出栈的时候，同时pop辅助栈。
#!/usr/bin/env python
# -*- coding:utf-8 -*-
"""
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
分析：这是去年google的一道面试题。
"""
class MinStack(object):
def __init__(self):
self.data = []
self.minIndex = []
def top(self):
return self.data[-1]
def push(self, value):
self.data.append(value)
if not self.minIndex:
self.minIndex.append(0)
else:
if value < self.data[self.minIndex[-1]]:
self.minIndex.append(len(self.data) - 1)
else:
self.minIndex.append(self.minIndex[-1])
self.dump()
def pop(self):
value = self.data.pop()
self.minIndex.pop()
self.dump()
return value
def min(self):
return self.data[self.minIndex[-1]]
def dump(self):
print str(self.data).ljust(20), str(self.minIndex).ljust(20), str(self.min()).ljust(20)
if __name__ == '__main__':
stack = MinStack()
print "Stack".ljust(20), "MinStack".ljust(20), "Min".ljust(20)
stack.push(3)
stack.push(4)
stack.push(2)
stack.push(1)
stack.pop()
stack.pop()
stack.push(5)
stack.push(0)
结果
Stack MinStack Min [3] [0] 3 [3, 4] [0, 0] 3 [3, 4, 2] [0, 0, 2] 2 [3, 4, 2, 1] [0, 0, 2, 3] 1 [3, 4, 2] [0, 0, 2] 2 [3, 4] [0, 0] 3 [3, 4, 5] [0, 0, 0] 3 [3, 4, 5, 0] [0, 0, 0, 3] 0