python 的 list 效率底下？

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

def

element

Stack

43 条回复 • 2014-11-12 17:01:00 +08:00

Altynai

2014-11-11 20:13:04 +08:00

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

takato

2014-11-11 20:41:20 +08:00 via iPhone

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

bcxx

2014-11-11 21:07:48 +08:00

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

wheatcuican

2014-11-11 21:21:13 +08:00

大力哥好！

wzzyj8

2014-11-11 22:58:35 +08:00

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

bcxx

2014-11-11 23:47:32 +08:00

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

staticor

2014-11-12 00:20:04 +08:00

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

ivanlw

2014-11-12 00:55:48 +08:00

好经典的蒂姆

rwalle

2014-11-12 07:33:40 +08:00 via Android

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

ryd994

2014-11-12 07:59:21 +08:00 via Android

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

ryd994

2014-11-12 07:59:46 +08:00 via Android

pop可能要重新sort

openroc

2014-11-12 08:27:18 +08:00

来个O(1) ;)

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

gt11799

2014-11-12 08:37:29 +08:00

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

msg7086

2014-11-12 08:48:59 +08:00

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

fkue0487

2014-11-12 08:52:05 +08:00

不是有个min函数么.

xcv58

2014-11-12 08:57:30 +08:00 via Smartisan T1

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

rrfeng

2014-11-12 09:26:15 +08:00

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

zhchbin

2014-11-12 09:28:59 +08:00

```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

2014-11-12 09:30:35 +08:00

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

frankzeng

2014-11-12 09:35:24 +08:00

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

zhchbin

2014-11-12 09:42:49 +08:00

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

ryanking8215

2014-11-12 09:58:23 +08:00

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

scorpius

2014-11-12 10:19:02 +08:00

@openroc 感觉这个正解

happywowwow

2014-11-12 10:38:16 +08:00

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

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

ipconfiger

2014-11-12 10:44:03 +08:00

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

janstk

2014-11-12 10:44:35 +08:00 via iPhone

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

frankzeng

2014-11-12 11:49:04 +08:00

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

openroc

2014-11-12 12:46:25 +08:00

gist被墙了。呵呵

openroc

2014-11-12 12:48:09 +08:00

@frankzeng 请科学上网。:)

takato

2014-11-12 12:49:40 +08:00

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

yakiang

2014-11-12 13:09:34 +08:00

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

ChanneW

2014-11-12 13:20:03 +08:00

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

caiych

2014-11-12 13:47:05 +08:00

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

bcxx

2014-11-12 14:09:15 +08:00

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

2014-11-12 14:13:32 +08:00

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

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

hellove1985

2014-11-12 14:28:50 +08:00

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

怎么贴上去的

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

caiych

2014-11-12 14:36:00 +08:00

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

takato

2014-11-12 15:30:28 +08:00

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

takato

2014-11-12 15:35:23 +08:00

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

ryanking8215

2014-11-12 15:46:11 +08:00

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

ryanking8215

2014-11-12 16:00:56 +08:00

@zhchbin 确实看错了，:)

dingyaguang117

2014-11-12 16:52:41 +08:00

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

pop:
-> pop tuple(num, min)

janstk

2014-11-12 17:01:00 +08:00

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