题目
Design a stack that supports push, pop, top, and retrievingthe minimum element in constant time.
答案:
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
1
Altynai 2014-11-11 20:13:04 +08:00 1
你getMin复杂度都O(nlogn)了,题目说了**constant time**
|
2
takato 2014-11-11 20:41:20 +08:00 via iPhone 1
常数级复杂度,只要额外维持一个最小值就可以了
|
4
wheatcuican 2014-11-11 21:21:13 +08:00
大力哥好!
|
5
wzzyj8 2014-11-11 22:58:35 +08:00
getmin用list改用tuple,至少快10倍。
|
7
staticor 2014-11-12 00:20:04 +08:00
另外生成一个最小栈, push时比一下.
|
8
ivanlw 2014-11-12 00:55:48 +08:00 1
好经典的蒂姆
|
9
rwalle 2014-11-12 07:33:40 +08:00 via Android
目测楼主以前没学过编程?经验太少 getMin这么简单的事情用sort就是杀鸡用牛刀
|
10
ryd994 2014-11-12 07:59:21 +08:00 via Android
每次插入都和当前最小比较一下,小于就换
每次pop就要重新sort了 |
11
ryd994 2014-11-12 07:59:46 +08:00 via Android
pop可能要重新sort
|
12
openroc 2014-11-12 08:27:18 +08:00
|
13
gt11799 2014-11-12 08:37:29 +08:00
题主是只想实现一个可以取最小值的栈?
heapq是一个最小堆,内部应该是一个二叉树,父节点始终小于子节点,因此顶点是最小的数。每当取出一个值,则两个子节点对比,小的上升。(实际上不是如此,不过这样容易理解) 可以先使用heapq把这个类实现了,然后试试看,自己能不能写一个最小堆? |
15
fkue0487 2014-11-12 08:52:05 +08:00
不是有个min函数么.
|
16
xcv58 2014-11-12 08:57:30 +08:00 via Smartisan T1
人家要 O(1) 你给弄个 O(n log n) Python 躺枪啊。
|
17
rrfeng 2014-11-12 09:26:15 +08:00
维护『一个』最小值的话 pop 了咋办?
|
18
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,不知道写对了木有。 |
19
zhchbin 2014-11-12 09:30:35 +08:00
囧。。还以为支持Mardown直接回复了。。自行缩进吧。
|
20
frankzeng 2014-11-12 09:35:24 +08:00
return min(self.L)不就行了吗,干嘛自己实现?
|
22
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)呢? |
24
happywowwow 2014-11-12 10:38:16 +08:00
o(1)的如何实现? 每次push的时候维护一个最小值?但请问pop的时候不是需要查询是否这个维护的值被pop了么?又需要重新找出最小的
感觉得 双栈 或者 一栈一最小堆 |
25
ipconfiger 2014-11-12 10:44:03 +08:00
leetcode 里用Python写的话一个栈就Memory溢出了,2个还不爆浆?
|
26
janstk OP 双栈的话会超出内存限制。无语了
|
27
frankzeng 2014-11-12 11:49:04 +08:00
@openroc https://gist.github.com/openroc/196642a254a542e4e80f.js 这一个请求是不是你弄的?这一串东西把整个贴拉到奇慢无比,这算不算是v2ex的bug呢?
|
28
openroc 2014-11-12 12:46:25 +08:00
gist被墙了。呵呵
|
31
yakiang 2014-11-12 13:09:34 +08:00
我能说这是上个月珍爱网校招数据岗位的一道笔试题吗
|
32
ChanneW 2014-11-12 13:20:03 +08:00
我的第一想法是, 拖慢 pop push 速度,每次操作都更新最小值. 反而获取最小值只是把值返回.
这样应该能过机器测试了,懒人的程序只做到刚好能用. |
33
caiych 2014-11-12 13:47:05 +08:00
跟python和list都没什么关系……
LZ需要学习一下基本的数据结构…这东西叫堆或者优先队列什么的… --- Python自带的优先队列居然没有top或者front这样的方法…只能拿出来看…… |
34
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 了吧…… |
35
zhchbin 2014-11-12 14:13:32 +08:00
|
36
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> |
39
takato 2014-11-12 15:35:23 +08:00
双栈可以的原因是因为栈不能pop任意位置,而只能pop顶,所以只需要发现目前值小于等于当前最小值的时候,push一个最小值的栈则可,否则就不push。
pop的时候先检验最小堆栈顶是不是这个元素,是则pop,否则不变 |
40
ryanking8215 2014-11-12 15:46:11 +08:00
@yakiang 这是leetcode上的题,主要是要求各操作都是O(1)的时间复杂度
|
41
ryanking8215 2014-11-12 16:00:56 +08:00
@zhchbin 确实看错了,:)
|
42
dingyaguang117 2014-11-12 16:52:41 +08:00
pair的单栈,哈哈 就是比较浪费空间,有些最小值不必要存~
push: -> push tuple(num, min) pop: -> pop tuple(num, min) |
43
janstk OP 好吧终于过了,感谢上面回复的各位。
|