-
Notifications
You must be signed in to change notification settings - Fork 90
Expand file tree
/
Copy pathmin_stack.py
More file actions
95 lines (72 loc) · 2.24 KB
/
min_stack.py
File metadata and controls
95 lines (72 loc) · 2.24 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
# coding: utf-8
"""
https://leetcode.com/problems/min-stack/
"""
class MinStack:
def __init__(self):
self.array = []
def push(self, x: int) -> None:
self.array.append(x)
def pop(self) -> None:
self.array.pop()
def top(self) -> int:
return self.array[-1]
def getMin(self) -> int:
return min(self.array)
class MinStack2:
def __init__(self):
self.stack = []
# We use an extra variable to track the minimum value.
self.min_value = float('inf')
def push(self, x: int) -> None:
self.stack.append(x)
if x < self.min_value:
self.min_value = x
def pop(self) -> None:
popped = self.stack.pop()
if popped == self.min_value:
if self.stack:
self.min_value = min(self.stack)
else:
self.min_value = float('inf')
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
if self.min_value == float('inf'):
return self.stack[0]
return self.min_value
class MinStack3:
def __init__(self):
self.stack = []
# We keep track of the minimum value for each push(),
# and push the minimum value into track_stack.
# NOTE: The length of both stacks are always equal.
# https://www.geeksforgeeks.org/tracking-current-maximum-element-in-a-stack/
self.track_stack = []
def push(self, x: int) -> None:
self.stack.append(x)
try:
current_min = self.track_stack[-1]
except IndexError:
self.track_stack.append(x)
else:
if x < current_min:
# There is a new minimum value.
current_min = x
else:
# The minimum is still the same as the last push().
pass
self.track_stack.append(current_min)
def pop(self) -> None:
self.stack.pop()
self.track_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.track_stack[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()