411. Widest Ramp
A hiker studies a trail described by the array nums, where nums[i] is the elevation at checkpoint i. A ramp is a pair of checkpoints (i, j) with i < j and nums[i] <= nums[j], so the second checkpoint is at least as high as the first. The width of the ramp is j - i.
Return the width of the widest ramp in the trail, or 0 if no ramp exists. Checking all pairs takes O(n^2) time. Notice that only certain checkpoints can ever be the best left end of a ramp, and that a stack can collect them before you sweep from the right.
Example 1
- Input:
- nums = [8,3,5,1,6,2,7,0]
- Output:
- 5
- Explanation:
Checkpoints 1 (value 3) and 6 (value 7) form a ramp of width 5. A wider pair does not exist, for example no later checkpoint reaches 8.
Example 2
- Input:
- nums = [9,7,4,2]
- Output:
- 0
- Explanation:
The trail only goes down, so there is no ramp and the answer is 0.
Constraints
1 ≤ nums.length ≤ 105
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)