Introduction
A monotonic stack is a stack that maintains the elements in a way that preserves their monotonic order. Monotonic stacks are often used in problems that require finding the next greater or smaller element for each element in an array in time.
Implementation
A generic template
stack = []
for i, x in enumerate(arr):
while stack and stack[-1] 'OPERATOR' x:
// if the previous condition is satisfied, we pop the top element
stackTop = stack.pop()
// nextGreater[stackTop] = i
if stack:
// prevGreater[i] = stackTop
stack.append(i)
Find next greater element
N = len(arr)
stack = []
nextGreater = [-1] * N
for i, x in enumerate(arr):
// maintain decreasing monotonic stack
while stack and x > arr[stack[-1]]:
stackTop = stack.pop()
nextGreater[stackTop] = i
stack.append(i)
Find previous greater element
N = len(arr)
stack = []
prevGreater = [-1] * N
for i, x in enumerate(arr):
// maintain decreasing monotonic stack
while stack and x >= arr[stack[-1]]:
stack.pop()
if stack:
prevGreater[i] = stack[-1]
stack.append(i)
Find next smaller element
N = len(arr)
stack = []
nextSmaller = [-1] * N
for i, x in enumerate(arr):
// maintain increasing monotonic stack
while stack and x < arr[stack[-1]]:
stackTop = stack.pop()
nextSmaller[stackTop] = i
stack.append(i)
Find previous smaller element
N = len(arr)
stack = []
prevSmaller = [-1] * N
for i, x in enumerate(arr):
// maintain increasing monotonic stack
while stack and x <= arr[stack[-1]]:
stackTop = stack.pop()
if stack:
prevSmaller[i] = stack[-1]
stack.append(i)
Summary
Problem | Stack Type | Operator in while loop | Assignment Position |
---|---|---|---|
next greater | decreasing (equal allowed) | stackTop < current | inside while loop |
previous greater | decreasing (strict) | stackTop ⇐ current | outside while loop |
next smaller | increasing (equal allowed) | stackTop > current | inside while loop |
previous smaller | increasing (strict) | stackTop >= current | outside while loop |
- next greater decreasing (equal allowed)
stackTop < current
inside while loop - previous greater decreasing (strict)
stackTop <= current
outside while loop - next smaller increasing (equal allowed)
stackTop > current
inside while loop - previous smaller increasing (strict)
stackTop >= current
outside while loop
Complexity
- Time complexity:
- Space complexity: