A stack that stays sorted (increasing or decreasing). As you scan through an array, pop elements that violate the order — each pop reveals useful info like "next smaller element." O(n) total.
What Is It?
You process elements left to right, maintaining a stack that is always in sorted order (monotonically increasing or decreasing). When a new element would violate the order, you pop from the stack until the order is restored, then push the new element.
The key insight: when you pop an element, you've just found something meaningful about it. In a monotonically increasing stack, when you pop element j because of element i, you've discovered that nums[i] is the "next smaller element" for nums[j].