-
Notifications
You must be signed in to change notification settings - Fork 2
/
minimum-stack.py
92 lines (75 loc) · 2.13 KB
/
minimum-stack.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
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
# https://leetcode.com/problems/min-stack/
# Design a stack that supports push, pop, top, and retrieving the 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.
# solution explanation : http://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.mainStack = []
self.minStack = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
if len(self.mainStack) == 0:
self.mainStack.append(x)
self.minStack.append(x)
else:
self.mainStack.append(x)
y = self.minStack[len(self.minStack)-1]
if x < y:
self.minStack.append(x)
else:
self.minStack.append(y)
def pop(self):
"""
:rtype: void
"""
self.mainStack.pop()
self.minStack.pop()
def top(self):
"""
:rtype: int
"""
#print len(self.mainStack)
# print self.minStack
return self.mainStack[len(self.mainStack)-1]
def getMin(self):
"""
:rtype: int
"""
return self.minStack[len(self.minStack)-1]
def print_stack(self):
print "minstack=" , self.minStack
print "mainStack" , self.mainStack
print "=========================="
my_minstack = MinStack()
my_minstack.print_stack()
my_minstack.push(-2)
my_minstack.print_stack()
print my_minstack.top()
my_minstack.print_stack()
# my_minstack.push(6)
# my_minstack.push(15)
# my_minstack.push(56)
# my_minstack.print_stack()
# my_minstack.push(1)
# my_minstack.print_stack()
# my_minstack.push(0)
# my_minstack.print_stack()
# my_minstack.push(10)
# my_minstack.print_stack()
# my_minstack.pop()
# my_minstack.print_stack()
# my_minstack.pop()
# my_minstack.print_stack()
# my_minstack.push(80)
# my_minstack.print_stack()
#print my_minstack.getMin()