A monotonic stack is a data structure that maintains elements in a specific order (either increasing or decreasing) as they are processed. It is particularly useful for solving problems like next greater element, previous smaller element, or other similar scenarios.
Next Greater Element
def next_greater_element(nums):
stack = [] # Monotonic decreasing stack
result = [-1] * len(nums) # Default value is -1
for i in range(len(nums) - 1, -1, -1): # Traverse from right to left
while stack and stack[-1] <= nums[i]:
stack.pop() # Remove smaller elements
if stack:
result[i] = stack[-1] # Next greater element is on top
stack.append(nums[i]) # Push the current element
return result
Next Lesser Element
def next_lesser_element(nums):
stack = [] # Monotonic increasing stack
result = [-1] * len(nums) # Default value is -1
for i in range(len(nums) - 1, -1, -1): # Traverse from right to left
while stack and stack[-1] >= nums[i]:
stack.pop() # Remove larger or equal elements
if stack:
result[i] = stack[-1] # Next lesser element is on top
stack.append(nums[i]) # Push the current element
return result
Previous Smaller Element
def previous_smaller_element(nums):
stack = [] # Monotonic increasing stack
result = [-1] * len(nums) # Default value is -1
for i in range(len(nums)): # Traverse from left to right
while stack and stack[-1] >= nums[i]:
stack.pop() # Remove larger elements
if stack:
result[i] = stack[-1] # Previous smaller element is on top
stack.append(nums[i]) # Push the current element
return result
Previous Larger Element
def previous_larger_element(nums):
stack = [] # Monotonic decreasing stack
result = [-1] * len(nums) # Default value is -1
for i in range(len(nums)): # Traverse from left to right
while stack and stack[-1] <= nums[i]:
stack.pop() # Remove smaller or equal elements
if stack:
result[i] = stack[-1] # Previous larger element is on top
stack.append(nums[i]) # Push the current element
return result