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)不就行了吗，干嘛自己实现?

[zhchbin]

@frankzeng min(self.L) 的复杂度应该是O(n)。

[ryanking8215]

@zhchbin 好像不对吧，pop的时候，你怎么知道当前pop的那个值，在min_data里也需要pop掉，也即最大的那个？
self.min_data.append(min(self.min_data[-1], x))
这个明显不是O(1)，怎么保证push是O(1)呢？

[scorpius]

@openroc 感觉这个正解

[happywowwow]

o(1)的如何实现？ 每次push的时候维护一个最小值？但请问pop的时候不是需要查询是否这个维护的值被pop了么？又需要重新找出最小的

感觉得 双栈 或者 一栈一最小堆

[ipconfiger]

leetcode 里用Python写的话一个栈就Memory溢出了，2个还不爆浆？

[janstk]

双栈的话会超出内存限制。无语了

[frankzeng]

@openroc https://gist.github.com/openroc/196642a254a542e4e80f.js 这一个请求是不是你弄的？这一串东西把整个贴拉到奇慢无比，这算不算是v2ex的bug呢?

[openroc]

gist被墙了。呵呵

[openroc]

@frankzeng 请科学上网。:)

[takato]

@bcxx 感谢- -。笔误- -。。

[yakiang]

我能说这是上个月珍爱网校招数据岗位的一道笔试题吗

[ChanneW]

我的第一想法是, 拖慢 pop push 速度,每次操作都更新最小值. 反而获取最小值只是把值返回.
这样应该能过机器测试了,懒人的程序只做到刚好能用.

[caiych]

跟python和list都没什么关系……
LZ需要学习一下基本的数据结构…这东西叫堆或者优先队列什么的…
---
Python自带的优先队列居然没有top或者front这样的方法…只能拿出来看……

[bcxx]

https://github.com/bcho/homework/blob/master/oj/leetcode/min_stack.py 的确是用两个 list 就可以过啊……


@caiych 用优先队列也不是 O(1) 的…… 另外用 https://docs.python.org/2/library/heapq.html#heapq.nsmallest 这个就可以获取 top 和 front 了吧……

[zhchbin]

@ipconfiger @janstk 双栈可以过啊。。在上面的版本做空间上的优化。

@ryanking8215 其实估计是排版的问题导致你没看清楚代码逻辑，懒得解释哈。

[hellove1985]

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

怎么贴上去的

<script src=https://gist.github.com/openroc/196642a254a542e4e80f.js></script>

[caiych]

@bcxx
重新读了一遍题，发现想当然了。。。

[takato]

@gt11799 堆的插入操作是O(logn)的

[takato]

双栈可以的原因是因为栈不能pop任意位置，而只能pop顶，所以只需要发现目前值小于等于当前最小值的时候，push一个最小值的栈则可，否则就不push。
pop的时候先检验最小堆栈顶是不是这个元素，是则pop，否则不变

[ryanking8215]

@yakiang 这是leetcode上的题，主要是要求各操作都是O(1)的时间复杂度

[ryanking8215]

@zhchbin 确实看错了，:)

[dingyaguang117]

pair的单栈，哈哈 就是比较浪费空间，有些最小值不必要存~
push:
-> push tuple(num, min)

pop:
-> pop tuple(num, min)

[janstk]

好吧终于过了，感谢上面回复的各位。