Monotonic stack is a data structure that maintains elements in a monotonic order to optimize certain types of problems, particularly those involving ranges or nearest greater/smaller elements.
All the basic operations of a stack can be applied to a monotonic stack, but with additional constraints to maintain the monotonic property. The common operations include:
- Push: When pushing a new element onto the stack, elements that violate the monotonic property are popped off first. For an increasing monotonic stack, elements greater than the new element are removed; for a decreasing monotonic stack, elements smaller than the new element are removed.
- Pop, top, isEmpty: These operations function the same way as in a regular stack.
The elements stored in a monotonic stack must be comparable.
Monotonic stack is particularly useful for solving problems that involve finding the next or previous greater/smaller element in an array or sequence. The stack is sort of greedy algorithm, so it can only give local solutions. The problem must be the nearest one.
The stack can be constructed by sweeping through the array from left to right or from right to left. Along the way, some information can be collected from the stack status like the top element or auxillary variables, to solve the problem.