最大间隔问题

给定数组 a,求下标对 i, j 满足 a[i] <= a[j],并且 j - i 最大

分析

  • 假设目前最优解是 d,对于 j,至少要检查 i = j - d - 1 才可能最优
  • 记录前缀最小值 p[x] = min{p[0..x]}
  • 倒着循环 j,对于每个 j 看一下 p[j-d-1] 是否 <= a[j],用 p 引导,这里指的是通过 p 可以知道在这个 i 之前还有没有比 a[j] 更小的
  • 如果前面都比 a[j] 大,则这个 j 得不到更优的解

时间 O(n) 因为内层循环的值(best)始终在增大,一共循环了 n 次。

int run(vector<int> &a){
    int n = a.size();
    vector<int> p(n);
    for (int i = 0; i < n; i++){
        p[i] = ((i == 0) || (a[i] < p[i - 1])) ? a[i] : p[i - 1];
    }
    int best = 0;
    for (int j = n - 1; j > best; j--){
        while ((j > best) && (a[j] >= p[j - best - 1])){
            ++ best;
        }
    }
    return best;
}