Monotonic Stack Pattern
Apply the monotonic stack to solve daily-temperatures, largest-rectangle-in-histogram, and next-greater-element in O(n).
What Is a Monotonic Stack?
A monotonic stack is a stack that maintains a sorted invariant across its elements. An increasing monotonic stack has elements increasing from bottom to top; a decreasing monotonic stack has elements decreasing from bottom to top. When a new element violates the invariant, elements are popped until the invariant is restored, and then the new element is pushed.
This simple mechanism enables O(n) answers to 'nearest greater element' and 'nearest smaller element' queries that would naively require O(n²) nested loops.
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)Next Greater Element (LeetCode 496)
For each element, find the first element to its right that is strictly greater. A brute force O(n²) scans rightward from each position. The monotonic stack approach: maintain a decreasing stack of indices. When a larger element is encountered, pop all smaller indices — their 'next greater' is the current element. Remaining indices have no next greater element (answer is -1).
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]