Problem:962. 最大宽度坡

思路：可以先保留原有位置信息排序一下，这样可以减低一个维度，只需要考虑排序完后的原先的索引值，遍历一遍排序后数组，维护一个最小索引值，每次遍历到一个数就取一个max即可。

Accode:

class Solution {
    static bool cmp(pair<int, int> a, pair<int, int> b) { 
        // if(a.first==b.first) return a.second<b.second;
        return a.first<b.first || a.first==b.first && a.second<b.second;
     }
public:

    int maxWidthRamp(vector<int>& nums) {
        int ans = 0;
        vector<pair<int, int>> cp;
        for (int i = 0; i < nums.size(); i++) {
            cp.push_back({nums[i], (int)cp.size()});
        }
        sort(cp.begin(), cp.end(),cmp);
        int min_idx = 1e9;
        for (auto item : cp) {
            auto [val, idx] = item;
            if (idx < min_idx)
                min_idx = idx;
            if (idx > min_idx)
                ans = max(ans, idx - min_idx);
        }
        return ans;
    }
};

时间复杂度：主要是排序$o(n*logn)$

方法二:
思路：对于每个i和j，假设nums[i]<=nums[j]，如果存在一个k使得nums[j]<=nums[k] && j<k;那么选i绝对会比选j更好，因为nums[i]<=nums[j]<=nums[k]，k-i>k-j；所以这样我们可以知道，可能成为答案区间左端点区间的索引值肯定是递减的，刚好我们可以用单调栈存储这些递减的索引值，最后我们在从后往前枚举一遍和栈顶比较更新答案最大值就好了。

Accode:

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        stack<int> sta;
        for(int i=0;i<nums.size();i++){
            if(sta.size()==0 || nums[sta.top()]>nums[i]){
                sta.push(i);
            }
        }
        int ans = 0;
        for(int i=nums.size()-1;i>=0;i--){
            while(sta.size() && nums[sta.top()]<=nums[i]){
                ans = max(ans,i-sta.top());
                sta.pop();
            }
        }
        return ans;
    }
};

时间复杂度:$o(n)$

方法三：
方法二是从后往前枚举，我们也可以从前往后枚举，因为是有序的栈，所以我们可以二分查找，离他最远的左端点。
ps:如果忘了二分可以去复习一下。 传送门
Accode:

class Solution {
public:
    int binary_find(vector<int>& nums, vector<int>& sta, int t) {
        int l = -1, r = sta.size();
        while (l + 1 != r) {
            int mid = (l + r) >> 1;
            if (nums[sta[mid]] <= t) {
                r = mid;
            } 
            else{
                l = mid;
            }
        }
        cout <<r <<endl;
        return r;
    }
    int maxWidthRamp(vector<int>& nums) {
        vector<int> sta;
        for (int i = 0; i < nums.size(); i++) {
            if (sta.size() == 0 || nums[sta.back()] > nums[i]) {
                sta.push_back(i);
            }
        }
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            int idx = binary_find(nums, sta, nums[i]);
            // cout << idx<<endl;
            if(idx!=sta.size()) ans = max(ans, i - sta[idx]);

        }
        return ans;
    }
};