Augment stack to support O(1) getMin/getMax or use a deque for window min/max
Track running min/max alongside values or use monotonic deque for window extrema.
Use for min stack design, and sliding window extrema in arrays.
Augment each push with the running min/max to support O(1) queries; use a monotonic deque for window extrema.
# Min/Max Stack Templates
class MinStack:
def __init__(self):
self.st=[]
def push(self, x:int)->None:
cur_min = x if not self.st else min(x, self.st[-1][1])
self.st.append((x, cur_min))
def pop(self)->None:
self.st.pop()
def top(self)->int:
return self.st[-1][0]
def getMin(self)->int:
return self.st[-1][1]Maintain paired min with each push
class MinStack:
def __init__(self): self.st=[]
def push(self, x): self.st.append((x, x if not self.st else min(x, self.st[-1][1])))
def pop(self): self.st.pop()
def top(self): return self.st[-1][0]
def getMin(self): return self.st[-1][1]Deque for window min/max
from collections import deque
class MonotonicQueue:
def __init__(self): self.dq = deque()
def push(self, x):
while self.dq and self.dq[-1] < x: self.dq.pop()
self.dq.append(x)
def pop(self, x):
if self.dq and self.dq[0] == x: self.dq.popleft()
def max(self): return self.dq[0] if self.dq else NoneEach operation is O(1).
Stack/deque holds elements.