All problems

Maximum Width Ramp

Medium · monotonic-stack

You are given a list of integers nums. A ramp is a pair of positions (i, j) with i < j and nums[i] <= nums[j]: the value at the start is no larger than the value at the end. The width of a ramp is j - i.

Return the largest width of any ramp in nums. If the list has no ramp at all, return 0.

Examples

Example 1

Input: nums = [5, 3, 4, 1, 2, 6, 2]

Output: 5

Positions 0 and 5 hold 5 and 6, and 5 <= 6, so that ramp has width 5. No ramp can be wider, because the list has only seven positions and position 6 holds 2, which is smaller than 5.

Example 2

Input: nums = [4, 3, 2, 1]

Output: 0

The values only go down, so no pair has a start that is at most its end.

Example 3

Input: nums = [2, 2, 2]

Output: 2

Equal values count: positions 0 and 2 form a ramp of width 2.

Constraints