Monotonic Stack: The Next Greater Element

Concepts: pyMonotonicStack, pyNextGreater

The next greater element problem is the gateway to monotonic stacks. Given an array, for each element, find the next element to its right that is larger. Brute force: for each element, scan right until you find something larger. O(n squared). Monotonic stack: one pass, O(n). The key insight: use the stack to track elements that have not yet found their 'next greater' element. When a large element arrives, it resolves all smaller elements waiting in the stack. Next Greater Element — Step by Step Why the Stack is Monotonically Decreasing At every point in the algorithm, the stack always contains indices whose values are in decreasing order from bottom to top. This is why it is called a monotonic decreasing stack. Whenever a new element is larger than the stack top, we pop — because the new e