Find maximum width ramp: indices i < j where nums[i] <= nums[j]. Return j-i.
Input: nums=[6,0,8,2,1,5] → Output: 4. i=1,j=5: nums[1]=0 <= nums[5]=5.
Input: nums=[9,8,1,0,1,9,4,0,4,1] → Output: 7
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
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)