c++ - 在 O(n) 时间 O(n) 内存中计算 max(min(A[i .. i+d]))

Question

我有一个算法问题要求得到 max(min(A[i .. i+d]))在 O (n)时间。
通用解决方案:

int max = 0;
for( i = 0; i< n-d; i++){
  int min = MX;
  for( j = i; j < i + d; j++)
     if(min > A[j])
       min = A[j];
  if(max < min)
     max = min;
}
printf("%d\n", max);

但它需要 O(n x d) 而不是 O(n)

更好的解决方案:使用 Range_minimum_query

int max = 0;
for( i = 0; i< n-d; i++){
  int min = RMQ( i , i + d);
  if(max < min)
     max = min;
}
printf("%d\n", max);

需要 O(log(d) * n)因为 RMQ 的平均时间是 log(d)

我脑子里想了大约 15 天这个问题，但还没有装修。谁能有效地解决这个问题？

输入输出数据:1<n<10^7 1<d<n

input : n = 10, d = 3, A[i] > 0
1, 3, 2, 4, 5, 6, 7, 8, 9, 10
result : 8 //= max(1, 2, 2, 4, 5, 6, 7, 8)

Answer 1

在 Range minimum query 之后philosophy(这有利于随机访问)，我会使用 Double-ended queue (这有利于顺序访问)，它为所有操作提供了 O(1) 的平均复杂度^*。

*_{插入/删除除外)}