Repository navigation
Expand file tree
/
Copy path155_Min_Stack.py
More file actions
125 lines (113 loc) · 2.59 KB
/
Copy path155_Min_Stack.py
File metadata and controls
125 lines (113 loc) · 2.59 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
#!/usr/bin/env python3
# import DoubleLinkList
#
# class MinStack(object):
#
# def __init__(self):
# """
# initialize your data structure here.
# """
# self.PseudoHead = self.DoubleLinkList(-1)
# self.PseudoTail = self.PseudoHead
# self.MinList = []
# self.size = 0
#
#
# def push(self, x):
# """
# :type x: int
# :rtype: void
# """
# newNode = self.DoubleLinkList(x)
# newNode.next = self.PseudoTail.next
# newNode.pre = self.PseudoTail
# self.PseudoTail.next = newNode
#
# for i in range(self.size):
# if self.MinList[i].val > x:
# self.MinList.insert(i, newNode)
# break
# else:
# self.MinList.append(newNode)
#
# self.size += 1
#
# def pop(self):
# """
# :rtype: void
# """
# if self.size > 0:
# tmp = self.PseudoTail
# tmp.pre.next = None
# self.MinList.remove(tmp)
# self.size -= 1
#
# def top(self):
# """
# :rtype: int
# """
# if self.size > 0:
# tmp = self.PseudoTail
# return tmp.val
#
# def getMin(self):
# """
# :rtype: int
# """
#
# if self.size > 0:
# tmp = self.MinList.pop(0)
# tmp.pre.next = tmp.next
# tmp.next.pre = tmp.pre
# self.size -= 1
# return tmp.val
#
# class DoubleLinkList(object):
# def __init__(self, x):
# self.val = x
# self.pre = None
# self.next = None
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min = float('inf')
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.stack.append(x)
if self.min > x:
self.min = x
def pop(self):
"""
:rtype: void
"""
if len(self.stack) > 0:
self.stack.pop()
if len(self.stack) > 0:
self.min = min(self.stack)
else:
self.min = float('inf')
def top(self):
"""
:rtype: int
"""
if len(self.stack) > 0:
return self.stack[-1]
def getMin(self):
"""
:rtype: int
"""
if len(self.stack) > 0:
return self.min
ms = MinStack()
ms.push(1)
ms.push(20)
ms.push(4)
ms.pop()
print(ms.top())
print(ms.getMin())