I had an algorithm problem asking to get
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);
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)
log(d)
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)
Following the Range minimum query philosophy (which is good for random access), I would use a Double-ended queue (which is good for sequential access), which offers a average complexity of O(1) for all operations*.
*except insertion/deletion)