Minimum value of maximum values in sub-segments ... in O(n) complexity

There is a very clever way to do this that's related to this earlier question. The idea is that it's possible to build a queue data structure that supports enqueue, dequeue, and find-max in amortized O(1) time (there are many ways to do this; two are explained in the original question). Once you have this data structure, begin by adding the first k elements from the array into the queue in O(k) time. Since the queue supports O(1) find-max, you can find the maximum of these k elements in O(1) time. Then, continuously dequeue an element from the queue and enqueue (in O(1) time) the next array element. You can then query in O(1) what the maximum of each of these k-element subarrays are. If you track the minimum of these values that you see over the course of the array, then you have an O(n)-time, O(k)-space algorithm for finding the minimum maximum of the k-element subarrays.

Hope this helps!

@templatetypedef's answer works, but I think I have a more direct approach.

Start by computing the max for the following (closed) intervals:

[k-1, k-1]
[k-2, k-1]
[k-3, k-1]
...
[0, k-1]

Note that each of these can be computed in constant time from the preceeding one.

Next, compute the max for these intervals:

[k, k]
[k, k+1]
[k, k+2]
...
[k, 2k-1]

Now these intervals:

[2k-1, 2k-1]
[2k-2, 2k-1]
[2k-3, 2k-1]
...
[k+1, 2k-1]

Next you do the intervals from 2k to 3k-1 ("forwards intervals"), then from 3k-1 down to 2k+1 ("backwards intervals"). And so on until you reach the end of the array.

Put all of these into a big table. Note that each entry in this table took constant time to compute. Observe that there are at most 2*n intervals in the table (because each element appears once on the right side of a "forwards interval" and once on the left side of a "backwards interval").

Now, if [a,b] is any interval of width k, it must contain exactly one of 0, k, 2k, ...

Say it contains m*k.

Observe that the intervals [a, m*k-1] and [m*k ,b] are both somewhere in our table. So we can simply look up the max for each, and the max of those two values is the max of the interval [a,b].

So for any interval of width k, we can use our table to get its maximum in constant time. We can generate the table in O(n) time. Result follows.