题目

$max(j - i)$ 满足$a_j >= a_i$下

数据

Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
Output: 6  (j = 7, i = 1)

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Output: 8 ( j = 8, i = 0)

Input:  {1, 2, 3, 4, 5, 6}
Output: 5  (j = 5, i = 0)

Input:  {6, 5, 4, 3, 2, 1}
Output: -1 

rmax[i] 是i包含自己右边的最大的数,
lmin[i] 是i包含自己左边的最小的数。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 10;
ll a[maxn];
ll lmin[maxn];
ll rmax[maxn];
int main() {
    int T;
    cin >> T;
    while (T --) {
        int N;
        cin >> N;
        for (int i = 0; i < N; ++i) {
            scanf("%lld", &a[i]);
        }
        lmin[0] = a[0];
        for (int i = 1; i < N; ++i) {
            lmin[i] = min(lmin[i - 1], a[i]);
        }
        rmax[N - 1] = a[N - 1];
        for (int i = N - 2; i >= 0; --i) {
            rmax[i] = max(rmax[i + 1], a[i]);
        }
        int result = -1;
        int left = 0;
        for (int right = 0; right < N; ++right) {
            if (rmax[right] >= lmin[left]) {
                result = max(result, right - left);
            }
            while (left < right && lmin[left] > rmax[right]) {
                left ++;
            }
        }
        cout << result << endl;
    }
    return 0;
}

反题目

满足$j - i >= k$ 下，最大的$a_j - a_i$
先看k=0的情况，维护之前的最小值。然后一个for
那么k!=0的时候，维护前面[0, j - k]区间的最小值，然后一个for