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:

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:

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 * 104
• 0 <= nums[i] <= 5 * 104

---

Solutions

Solution 1

Intuition

1. build a array to store these index
2. sort these indexes by these numbers in increasing order
   1. if numbers are equal, small index is first
3. from left to right, find min index, and update ans

Code

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        vector<int> idx(nums.size());
        for (int i = 0; i < nums.size(); i++) idx[i] = i;
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            if (nums[a] == nums[b])
                return a < b;
            else
                return nums[a] < nums[b];
        });
        int min_idx = idx[0], res = 0;
        for (int i = 1; i < idx.size(); i++) {
            res = max(res, idx[i] - min_idx);
            min_idx = min(min_idx, idx[i]);
        }
        return res;
    }
};

Complexity

• Time: O(nlogn)
• Space: O(n)