-
Notifications
You must be signed in to change notification settings - Fork 0
/
#43.py
54 lines (40 loc) · 1.09 KB
/
#43.py
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
from collections import deque
class MaxStack:
def __init__(self):
self.normal_stack = deque()
self.max_stack = deque()
self.max = None
def push(self, val):
self.normal_stack.append(val)
if self.max is None:
self.max = val
self.max_stack.append(val)
elif val >= self.max:
self.max_stack.append(val - self.max)
self.max = val
def pop(self):
assert len(self.normal_stack) > 0
val = self.normal_stack[-1]
self.normal_stack.pop()
if len(self.normal_stack) == 0:
self.max_stack.pop()
self.max = None
elif self.max == val:
diff = self.max_stack[-1]
self.max_stack.pop()
self.max = self.max - diff
return val
def get_max(self):
return self.max
max_stack = MaxStack()
while True:
args = input().split()
if len(args) == 1:
if args[0] == 'pop':
print("Pop returned: {0}".format(max_stack.pop()))
elif args[0] == 'max':
print("Current max: {0}".format(max_stack.get_max()))
elif args[0] == 'push':
print("Pushed {0} onto stack".format(args[1]))
max_stack.push(int(args[1]))
print()