962. Maximum Width Ramp

Posted on Edited on In

962. Maximum Width Ramp

Description

A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i.

Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.

Example 1:

1
2
3
Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.

Example 2:

1
2
3
Input: nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.

Constraints:

  • 2 <= nums.length <= 5 * 10^4
  • 0 <= nums[i] <= 5 * 10^4

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        vector<int> monotonic;
        int n = nums.size(), res = 0;
        for (int i = 0; i < n; i++) {
            if (monotonic.empty() || nums[i] < nums[monotonic.back()]) {
                monotonic.push_back(i);
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            while (!monotonic.empty() && nums[monotonic.back()] <= nums[i]) {
                res = max(res, i - monotonic.back());
                monotonic.pop_back();
            }
        }
        return res;
    }
};