962. Maximum Width Ramp

O(n) time O(n) space
小数在左边，大数在右边，对于右边每一个大数，尽可能找到左边第一个比大数小的数，所以在左边维护一个递减栈，所有可能的小数一定在这个栈里
greedy从后往前遍历每个数，对于每个数要找到从左边开始第一个不大于它的数，保存每个数字第一次出现的位置，而且依次只用保留最小的即可，比如[6, 0, 3]，只需要保存6和0即可，3在0的右边且大于0，则3永远不可能成为最优解，所以可以直接跳过

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

O(nlogn) time O(n) space

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        int n = A.size();
        vector<int> v(n);
        iota(begin(v), end(v), 0);
        auto cmp = [&A](int i, int j){return A[i] < A[j] || A[i] == A[j] && i < j;};
        sort(begin(v), end(v), cmp);
        int mn = INT_MAX, res = 0;
        for (int i : v) {
            mn = min(mn, i);
            res = max(res, i - mn);
        }
        return res;
    }
};

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        auto cmp = [&A](int i, int j){return A[i] < A[j] || A[i] == A[j] && i < j;};
        set<int, decltype(cmp)> s(cmp);
        int n = A.size();
        for (int i = 0; i < n; ++i) {
            s.insert(i);
        }
        int mn = INT_MAX, res = 0;
        for (int i : s) {
            mn = min(mn, i);
            res = max(res, i - mn);
        }
        return res;
    }
};