Overview
A Monotonic Stack is a specialized stack in which elements are kept in a consistent order. When a new element violates the required order, elements are removed from the top until the ordering condition is restored.
How it works
Process the input elements from left to right or in another specified direction.; Compare the current element with the element at the top of the stack.; Remove elements while they violate the required monotonic order.; Use removed elements to answer the relevant problem query when appropriate.; Push the current element or its index onto the stack.
Key concepts
Monotonic order; Stack operations; Next greater element; Next smaller element; Unresolved elements; Amortized analysis
Types
name: Monotonic Increasing Stack; description: Maintains elements in non-decreasing or strictly increasing order, depending on the problem's requirements.; name: Monotonic Decreasing Stack; description: Maintains elements in non-increasing or strictly decreasing order, depending on the problem's requirements.
Time complexity
operation: Processing the entire array; complexity: O(n) amortized; operation: Stack Push; complexity: O(1); operation: Stack Pop; complexity: O(1)
Space complexity
O(n) in the worst case.
Example
array: 2; 1; problem: Find the next greater element for each array position.; results: element: 2; nextGreater: 4; element: 1; nextGreater: 4; explanation: A decreasing stack stores unresolved elements. When a greater value appears, it resolves the next-greater-element queries for smaller elements at the top.