Monotonic Stack

A monotonic stack is a stack where the elements are always in a sorted order (either increasing or decreasing). This pattern is a powerful tool for efficiently solving problems that involve finding the 'next greater element', 'previous smaller element', or similar relationships in an array. Let's consider the 'Next Greater Element' problem: for each element in an array, find the first element to its right that is greater. A naive O(n^2) approach would use nested loops. A monotonic (specifically, a monotonically decreasing) stack provides an O(n) solution. We iterate through the array. For each element `x`, we look at the top of the stack. If the stack is not empty and `x` is greater than the element at the top of thestack, it means `x` is the 'next greater element' for the element at the top. So, we pop the stack and record this relationship. We keep popping until the stack is empty or the top element is greater than or equal to `x`. After this, we push `x` (or its index) onto the stack. This maintains the decreasing order of the stack. By the end of the single pass, we will have found the next greater element for all elements that had one. This pattern is versatile and can be adapted for many related problems.