python 的 list 效率底下？

[janstk]

题目

Design a stack that supports push, pop, top, and retrievingthe minimum element in constant time.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• getMin() – Retrieve the minimum element in the stack.

答案：

class MinStack:
    def __init__(self):
        self.L=[]
    def pop(self):
        return self.L.pop()
    def push(self,x):
        self.L.append(x)
    def top(self):
        return self.L[-1]
    def getMin(self):
        tmpL = self.L[:]
        tmpL.sort()
        return tmpL[0]

每次提示答案都超时…表吐槽，表示刚学python

[Altynai]

你getMin复杂度都O(nlogn)了，题目说了**constant time**

[takato]

常数级复杂度，只要额外维持一个最小值就可以了

[bcxx]

@takato 不是一个，是最小值的历史记录

[wheatcuican]

大力哥好！

[wzzyj8]

getmin用list改用tuple，至少快10倍。

[bcxx]

@wzzyj8 看题……不是 list 本身的问题- -

[staticor]

另外生成一个最小栈, push时比一下.

[ivanlw]

好经典的蒂姆

[rwalle]

目测楼主以前没学过编程？经验太少 getMin这么简单的事情用sort就是杀鸡用牛刀

[ryd994]

每次插入都和当前最小比较一下，小于就换
每次pop就要重新sort了

[ryd994]

pop可能要重新sort

[openroc]

来个O(1) ;)

https://gist.github.com/openroc/196642a254a542e4e80f

[gt11799]

题主是只想实现一个可以取最小值的栈？
heapq是一个最小堆，内部应该是一个二叉树，父节点始终小于子节点，因此顶点是最小的数。每当取出一个值，则两个子节点对比，小的上升。（实际上不是如此，不过这样容易理解）
可以先使用heapq把这个类实现了，然后试试看，自己能不能写一个最小堆？

[msg7086]

@gt11799
我看题目里的要求，应该不是说要做小顶堆吧。应该是双stack，一个维护数据，另一个维护最小值。

[fkue0487]

不是有个min函数么.

[xcv58]

人家要 O(1) 你给弄个 O(n log n) Python 躺枪啊。

[rrfeng]

维护『一个』最小值的话 pop 了咋办？

[zhchbin]

```python
class MinStack:
def __init__(self):
self.data = []
self.min_data = []

def pop(self):
if not self.data:
return None

self.min_data.pop()
return self.data.pop()

def push(self, x):
self.data.append(x)
if not self.min_data:
self.min_data.append(x)
else:
self.min_data.append(min(self.min_data[-1], x))

def top(self):
return None if not self.data else self.data[-1]

def getMin(self):
return None if not self.data else self.min_data[-1]

if __name__ == '__main__':
min_stack = MinStack()
data = [5, 2, 4, 3, -1, 0]
for val in data:
min_stack.push(val)
print min_stack.getMin()

min_stack.pop()
print min_stack.getMin()
min_stack.pop()
print min_stack.getMin()
```

经典的面试题目，刚学python，不知道写对了木有。

[zhchbin]

囧。。还以为支持Mardown直接回复了。。自行缩进吧。

[frankzeng]

return min(self.L)不就行了吗，干嘛自己实现?