题目描述

给定一个整数数组 A，_坡_是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。

找出 A 中的坡的最大宽度，如果不存在，返回 0 。

样例

输入：[6,0,8,2,1,5]
输出：4
解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.

输入：[9,8,1,0,1,9,4,0,4,1]
输出：7
解释：
最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.

注意

• 2 <= A.length <= 50000
• 0 <= A[i] <= 50000

算法1

(树状数组) $O(m + n \log m)$

1. 直接按照题意做，对于每个 A[i]，我们期望找到小于等于它的最小下标值。所以我们可以开一个长度为 $m=50001$ 的树状数组。
2. 每次查询下标小于等于 A[i] 中的最小值，然后用 i 来尝试更新 A[i]。
3. 注意，树状数组的下标必须从 1 开始。

时间复杂度

• $m$ 为 A 中的最大值，$n$ 次查询和更新操作，每次需要 $O(\log m)$ 的时间复杂度，故总共需要 $(m + n \log m)$ 的时间。可以通过离散化操作将 $m$ 压缩到 $n$。

C++ 代码

class Solution {
public:

    vector<int> f;

    void update(int x, int y) {
        for (; x <= 50001; x += x & -x)
            f[x] = min(f[x], y);
    }

    int query(int x) {
        int minr = 50001;
        for (; x; x -= x & -x)
            minr = min(minr, f[x]);
        return minr;
    }

    int maxWidthRamp(vector<int>& A) {
        int n = A.size();
        int ans = 0;

        f = vector<int>(50002, n + 1);

        for (int i = 0; i < n; i++)
            A[i]++;

        for (int i = 0; i < n; i++) {
            ans = max(ans, i - query(A[i]));
            update(A[i], i);
        }

        return ans;
    }
};

算法2

(二分) $O(n \log n)$

1. 我们维护一个可能作为答案左端点的数组 candidates，如果发现当前元素比 candidates 结尾的元素要大，则当前元素永远也不可能作为左端点。所以 candidates 是一个单调递减的数组。
2. 对于当前元素 A[i]，在 candidates 中二分查找第一个小于等于 A[i] 的元素 $j$，用 $j$ 的下标来更新答案即可。

时间复杂度

• 维护 candidates 只需要 $O(n)$ 的时间，每次二分需要 $O(\log n)$ 的时间，故总时间复杂度为 $O(n \log n)$。

C++ 代码

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        int n = A.size();
        vector<pair<int, int>> candidates;

        int ans = 0;

        candidates.push_back(make_pair(A[0], 0));

        for (int i = 0; i < n; i++) {
            int l = 0, r = candidates.size() - 1;

            while (l < r) {
                int mid = (l + r) >> 1;
                if (candidates[mid].first <= A[i])
                    r = mid;
                else
                    l = mid + 1;
            }

            if (candidates[l].first <= A[i])
                ans = max(ans, i - candidates[l].second);

            if (A[i] < candidates.rbegin() -> first)
                candidates.push_back(make_pair(A[i], i));
        }


        return ans;
    }
};

算法3

(线性扫描) $O(n)$

1. 维护一个前缀最小值数组 $minl$，和一个后缀最大值数组 $maxr$。例如，[6,0,8,2,1,5] 的两个数组分别为 [6,0,0,0,0,0], [8,8,8,5,5,5]。
2. 定义两个指针，初始时分别指向两个数组的开头，如果 minl[i] <= maxr[j]，则更新答案后 j++；否则 i++；
3. 解释：如果 minl[i] <= maxr[j]，则说明在 $i$ 之前（包括 $i$）必定有一个数字小于等于 $j$ 之后（包括 $j$）的某个数字。且左端的数字就是 $A[i]$，因为 $i$ 是从最小的开始往后走的，故此时只需要向后移动 $j$，去尝试 $j$ 之后的数字某个是否也可行。
4. 如果 minl[i] > maxr[j]，则说明 $i$ 之前（包括 $i$）的所有数字都比 $j$ 之后（包括 $j$）的所有数字要大，所以 $i$ 需要向后移动寻找一个小一些的数字。

时间复杂度

• 创建两个数组只需要 $O(n)$ 的时间，故总时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        int n = A.size();
        vector<int> minl(n, 50001), maxr(n, -1);

        int ans = 0;

        minl[0] = A[0];
        for (int i = 1; i < n; i++)
            minl[i] = min(minl[i - 1], A[i]);

        maxr[n - 1] = A[n - 1];
        for (int i = n - 2; i >= 0; i--)
            maxr[i] = max(maxr[i + 1], A[i]);


        int i = 0, j = 0;
        while (j < n) {
            if (minl[i] <= maxr[j]) {
                ans = max(ans, j - i);
                j++;
            }
            else
                i++;
        }

        return ans;
    }
};