Maximum Width Ramp

1. Build a Monotonic Decreasing Stack

• Iterate through the array from left to right
• Push index i onto the stack only if nums[i] is strictly less than the value at the current top of the stack
• This captures all candidate left endpoints — any optimal left index must appear in this decreasing sequence

2. Why Only Decreasing Values Are Candidates

• If nums[a] <= nums[b] and a < b, then a is always a better left endpoint than b (it gives a wider ramp)
• So we only need indices where values are strictly decreasing — later, larger-or-equal values are dominated by earlier ones

3. Traverse From Right to Left

• Start from the rightmost index j = n - 1 and move leftward
• For each j, check if nums[stack.top] <= nums[j]
• If so, pop the stack top as index i and record j - i as a candidate answer

4. Pop and Record Maximum Width

• Each time we pop, compute j - i and update maxWidth
• We can safely pop because no future (smaller) j could produce a wider ramp with this same i
• Continue popping while the condition holds — multiple left candidates may pair with the same j

5. Return the Result

• After the traversal completes, maxWidth contains the widest ramp found
• If no ramp exists (e.g., strictly decreasing array), maxWidth remains 0

Key Insight

The monotonic decreasing stack captures all useful left endpoints, and scanning from right to left ensures we try the widest possible ramp first for each candidate. Each index is pushed and popped at most once, giving O(n) time and O(n) space complexity.