155. Min Stack: with deque
The canonical way to solve this is by using two stacks. However, I have been using deque for so many times that I could not help but to think about solving it with a deque.
1class MinStack:
2
3 def __init__(self):
4 self.stack = []
5 self.track = deque()
6
7 def push(self, val: int) -> None:
8 self.stack.append(val)
9 if not self.track or val <= self.track[-1]:
10 self.track.append(val)
11 else:
12 self.track.appendleft(val)
13
14 def pop(self) -> None:
15 if self.stack:
16 temp = self.stack.pop()
17 if self.track[-1] == temp:
18 self.track.pop()
19 else:
20 self.track.popleft()
21
22 def top(self) -> int:
23 return self.stack[-1] if self.stack else None
24
25 def getMin(self) -> int:
26 return self.track[-1] if self.track else None
The gist of this deque is to fully utilize its O(1) trait for push and pop(peek) from either end.
We push and pop this deque together with stack, but we choose which end to push to. The deque is always intact in a way that the top of the stack must be either deque[0] or deque[-1] no matter when.
We only push to the right if val <= deque[-1], otherwise we push to the left. This promises us the current minimum element will always be deque[-1].
#Neetcode150 #Stack #Deque #Python