Repository navigation
Expand file tree
/
Copy pathminStack.py
More file actions
130 lines (108 loc) · 2.79 KB
/
Copy pathminStack.py
File metadata and controls
130 lines (108 loc) · 2.79 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#!/usr/bin/env python
#-*- coding: utf-8 -*-
import os,re,sys,commands,glob,json,collections,random,heapq
from random import randint
from LeetCodeUtils import *
class PriorityQueue:
def __init__(self):
self._queue = []
def push(self, item):
heapq.heappush(self._queue, item)
def pop(self):
return heapq.heappop(self._queue)
def top(self):
return self._queue[0]
def remove(self, item):
indexOfItem = self._queue.index(item)
if indexOfItem < 0 :
return False
self._queue[indexOfItem] = self._queue[-1]
self._queue.pop()
if indexOfItem < len(self._queue):
heapq._siftup(self._queue, indexOfItem)
return True
def verifyIsHeap(self):
t = self._queue[:]
heapq.heapify(t)
assert t == self._queue
def empty(self):
return len(self._queue) == 0
def __repr__(self):
return "PriorityQueue:"+str(self._queue)
pass
class MinStackSlow:
def __init__(self):
self.a = []
self.q = PriorityQueue()
pass
# @param x, an integer
# @return an integer
def push(self, x):
self.a.append(x)
self.q.push(x)
return x
# @return nothing
def pop(self):
x = self.a.pop()
removed = self.q.remove(x)
assert removed
# @return an integer
def top(self):
return self.a[-1]
# @return an integer
def getMin(self):
return self.q.top()
# refer to http://leetcode.com/2010/11/stack-that-supports-push-pop-and-getmin.html
class MinStack:
def __init__(self):
self.a = []
self.m = [] #MinStack
pass
# @param x, an integer
# @return an integer
def push(self, x):
self.a.append(x)
if not self.m or x <= self.m[-1]:
self.m.append(x)
return x
# @return nothing
def pop(self):
x = self.a.pop()
assert self.m[-1] <= x
if self.m[-1] == x:
self.m.pop()
# @return an integer
def top(self):
return self.a[-1]
# @return an integer
def getMin(self):
return self.m[-1]
def test():
a= MinStack()
a.push(1)
a.push(2)
assert a.getMin() == 1
assert a.top() == 2
assert a.a == [1, 2]
a.pop()
assert a.a == [1]
assert 1 == a.top()
a.pop()
a= MinStack()
for i in range(1, 1000):
a.push(randint(1, 100000))
for i in range(500):
a.pop()
# a.q.verifyIsHeap()
assert a.getMin() == min(a.a)
def testPush():
a = MinStack()
for i in range(1, 100000):
a.push(randint(1, 100))
def testPop():
a = MinStack()
for i in range(1, 100000):
a.push(randint(1, 100))
for i in range(1000):
a.pop()
pass