-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy path0155.Min_Stack.py
More file actions
111 lines (84 loc) Β· 2.74 KB
/
0155.Min_Stack.py
File metadata and controls
111 lines (84 loc) Β· 2.74 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
/*
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
*/
/*
there are two method to solve this problem
approch 1: we can use stack store the min value, each time we push number to stack, we store the min value in stack as well
approch 2: we use two stack, one can be use to store value, the other one can be use to store min value.
*/
#approach 2
class MinStack:
def __init__(self):
self.st = []
self.min_st = []
def push(self, val: int) -> None:
self.st.append(val)
if len(self.min_st) == 0 or val <= self.min_st[-1]:
self.min_st.append(val)
def pop(self) -> None:
if len(self.st) == 0:
raise IndexError("The stack is empty")
else:
val = self.st.pop()
if val == self.min_st[-1]:
self.min_st.pop()
return val
def top(self) -> int:
if len(self.st) == 0:
raise IndexError("The stack is empty")
return self.st[-1]
def getMin(self) -> int:
if len(self.st) == 0:
raise IndexError("The stack is empty")
return self.min_st[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
class MinStack:
def __init__(self):
self.st = []
def push(self, val: int) -> None:
self.st.append(val)
def pop(self) -> None:
if len(self.st) == 0:
raise IndexError("The stack is empty!")
return self.st.pop()
def top(self) -> int:
if len(self.st) == 0:
raise IndexError("The stack is empty!")
return self.st[-1]
def getMin(self) -> int: #注ζ沑ζθ―΄ε ι€ζε°εΌ
if len(self.st) == 0:
raise IndexError("The stack is empty!")
minValue = min(self.st)
return minValue
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()