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

Question

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

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天了，还没有装修。谁能有效解决这个问题？

i/o 数据：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 (which is good for random access), I would use a Double-ended queue（有利于顺序访问）之后，它为所有操作提供了 O(1) 的平均复杂度^*.

*_{除了insertion/deletion)}

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

calculating max(min(A[i .. i+d])) in O(n) time O(n) memory

c++

algorithm

loops

max

min