962. Maximum Width Ramp

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.

• binary search solution

class Solution {
    int helper(vector<int>& A, vector<int>& st, int num) {
        int l = 0, r = st.size() - 1, res = INT_MAX;
        while(l <= r) {
            int m = (l + r) / 2;
            if(A[st[m]] >= num) {
                res = min(res, m);
                r = m - 1;
            } else l = m + 1;
        }
        return res;
    }
public:
    int maxWidthRamp(vector<int>& A) {
        int n = A.size(), res = 0;
        vector<int> st;
        for(int i = n - 1; i >= 0; i--) {
            if(!st.empty() and A[st.back()] >= A[i]) {
                int j = helper(A, st, A[i]);
                res = max(res, st[j] - i);
            }
            if(st.empty() or A[st.back()] < A[i]) st.push_back(i);
        }
        return res;
    }
};

• ordered set solution

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        int n = nums.size();
        vector<pair<int, int>> A;
        set<int> s;
        for(int i = 0; i < n; i++) {
            s.insert(i);
            A.push_back({nums[i], i});
        }

        sort(begin(A), end(A));
        int res = 0;

        for(auto& [_, idx]: A) {
            res = max(res, *s.rbegin() - idx);
            s.erase(idx);
        }

        return res;
    }
};

• monotonic stack solution

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        int n = A.size(), res = 0;
        vector<int> st;
        for(int i = 0; i < n; i++) {
            if(st.empty() or A[st.back()] > A[i]) st.push_back(i);
        }
        for(int i = n - 1; i >= 0; i--) {
            while(!st.empty() and A[st.back()] <= A[i]) {
                res = max(res, i - st.back());
                st.pop_back();
            }
        }
        return res;
    }
};