Maximum Width Ramp

XXX. Maximum Width Ramp

Stack

Greedy

Problem Statement:

Given an array nums, find the maximum width ramp. A "ramp" is defined as a pair of indices i and j such that i <= j and nums[i] <= nums[j]. Return the maximum difference j - i where this condition holds true.

Algorithm:

1. Use a stack to store candidate indices for i in decreasing order of their values.
   • For every index i, if the stack is empty or nums[i] is smaller than the top of the stack, push i onto the stack.
2. Iterate backward over the array to find the largest valid j:
   • For each index j, pop from the stack while nums[j] >= nums[stack.peek()].
   • Update the maximum width ramp using the difference j - stack.pop().
3. Return the maximum width ramp.

Complexity:

Time Complexity: O(n), where n is the length of the array. Each element is pushed and popped at most once.
Space Complexity: O(n) due to the stack.

Java Implementation:

public int maxWidthRamp(int[] nums) {
    Stack stack = new Stack<>(); // Monotonic decreasing stack to store indices of potential "i"
    int max = -1; // Track the maximum width of the ramp

    // Step 1: Build the stack of indices with decreasing values
    for (int i = 0; i < nums.length; i++) 
        if (stack.isEmpty() || nums[i] < nums[stack.peek()]) 
            stack.push(i); // Push only when nums[i] is a new minimum

    // Step 2: Iterate from the end of the array and find the largest valid ramp
    for (int j = nums.length - 1; j >= 0; j--) 
        while (!stack.isEmpty() && nums[j] >= nums[stack.peek()]) 
            max = Math.max(max, j - stack.pop()); // Update max width and remove "used" index

    return max;
}
                

Explanation:

• **Building the Stack**: We construct a monotonic decreasing stack of indices by iterating from left to right. The stack ensures that the elements at the stored indices are strictly decreasing.
• **Finding the Ramp**: By iterating backward from the end of the array, we check if the current value satisfies the condition nums[i] <= nums[j]. If it does, we calculate the ramp width and update the maximum width.
• **Optimization**: Once an index is popped from the stack, it cannot contribute to a larger ramp, as we are moving leftward.