A monotonic stack is a stack data structure where the elements are in monotonic order that is either increasing order or decreasing order.
Basically, when pushing the element to stack, you check if this condition is meeting. If the condition is not met, pop those elements till you meet the condition. Then push the current element.
This concept is mainly used in problems like finding the next smallest element, next largest element, previous smallest element, or previous largest element. This concept is also used in histogram problems where the next largest/smallest height bar is to be found.
In Leetcode there are many problems under the tag of monotonic stack. One problem is the 132 pattern. Here indices should meet the criteria of i<j<k and elements should meet the criteria of nums[i] < nums[k] <nums[j].
This problem involves both finding the next largest element (nums[j]) and next smallest element (nums[k])
The below solution finds the min array before going to the stack approach. It uses right to left loop, so the monotonic stack of decreasing order is used:
Below is the brute-force approach solution:
