Maximum Width Ramp

Share

Find maximum width ramp: indices i < j where nums[i] <= nums[j]. Return j-i.

Example 1
Input: nums=[6,0,8,2,1,5] → Output: 4. i=1,j=5: nums[1]=0 <= nums[5]=5.
Example 2
Input: nums=[9,8,1,0,1,9,4,0,4,1] → Output: 7

Solution Approach

Monotonic stack of candidate left indices, then scan from right for best right match.

  • Build decreasing stack of indices from left (candidates for i)
  • Scan from right: for each j try to match top of stack
  • If nums[stack.top] <= nums[j]: record width, pop (greedy)
  • Continue until no match, move j left
  • Return max width
Java
public int maxWidthRamp(int[] nums) {
    int n = nums.length;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++)
        if (stack.isEmpty() || nums[stack.peek()] > nums[i]) stack.push(i);
    int max = 0;
    for (int j = n-1; j >= 0; j--) {
        while (!stack.isEmpty() && nums[stack.peek()] <= nums[j]) {
            max = Math.max(max, j - stack.pop());
        }
    }
    return max;
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)