Maintain increasing/decreasing stacks to find next/previous greater or smaller elements efficiently
Push indices/heights while maintaining monotonicity; pop when invariant breaks to resolve answers spanning the popped element.
Use for next greater/smaller queries, histogram rectangles, stock span, or removing digits for minimal number.
Next/previous greater or smaller via a monotone index stack; histogram area with a sentinel and width from the last lower bar.
# Monotonic Stack Template (Next Greater Element)
def next_greater(nums):
res = [-1]*len(nums)
st = [] # stack of indices
for i, v in enumerate(nums):
while st and nums[st[-1]] < v:
res[st.pop()] = v
st.append(i)
return res
# Largest Rectangle in Histogram (skeleton)
def largest_rectangle(heights):
st = []
max_area = 0
for i, h in enumerate(heights + [0]):
while st and heights[st[-1]] > h:
height = heights[st.pop()]
left = st[-1] + 1 if st else 0
max_area = max(max_area, height * (i - left))
st.append(i)
return max_areaPop while current breaks monotonic property to discover next boundary
def next_greater(nums):
res, stack = [-1] * len(nums), [] # stack of indices
for i, v in enumerate(nums):
while stack and nums[stack[-1]] < v:
res[stack.pop()] = v
stack.append(i)
return resUse increasing stack of heights; compute area when a lower bar appears
def largest_rectangle(heights):
st = [] # (index)
max_area = 0
for i, h in enumerate(heights + [0]):
while st and heights[st[-1]] > h:
height = heights[st.pop()]
left = st[-1] + 1 if st else 0
width = i - left
max_area = max(max_area, height * width)
st.append(i)
return max_areaMonotonic stack of decreasing prices to compute span
class StockSpanner:
def __init__(self):
self.st = [] # (price, span)
def next(self, price: int) -> int:
span = 1
while self.st and self.st[-1][0] <= price:
span += self.st.pop()[1]
self.st.append((price, span))
return spanEach element is pushed and popped at most once.
Stack may hold indices in worst case.