Monotonic Stack
https://www.geeksforgeeks.org/introduction-to-monotonic-stack-2/
A monotonic stack is a special data structure used in algorithmic problem-solving. Monotonic Stack maintaining elements in either increasing or decreasing order.
Where it's used?
Commonly used in problems to find the next greater or smaller element in an array etc.
Ex: this Sum of Subarrray minimums problem https://leetcode.com/problems/sum-of-subarray-minimums/editorial/
It’s quite simple actually, for a monotonically increasing stack, only push values as it increases.
- it there are values smaller than the top of the stack, you pop from the stack until the value is greater than the current top of the stack, or if the stack is empty