660. Max Width Ramp (Optimal)

Given an array nums, a ramp is a pair (i, j) with i < j and nums[i] <= nums[j]; its width is j - i. Return the maximum width over all ramps, or 0 if none exists, using an optimal O(n) stack method. The input is JSON {nums}.

Input: JSON {nums}.

Output: Integer — the maximum ramp width.

Examples

Input: {"nums":[6,0,8,2,1,5]}
Output: 4
Explanation: Indices 1 and 5.

Input: {"nums":[9,8,1,0,1,9,4,0,4,1]}
Output: 7
Explanation: Indices 2 and 9.

Input: {"nums":[5]}
Output: 0
Explanation: No pair.

Constraints

• 1<=n<=5*10^4

Asked by