Maximizing minimum on an array

There is prob开发者_StackOverflow中文版ably an efficient solution for this, but I'm not seeing it. I'm not sure how to explain my problem but here goes...

Lets say we have one array with n integers, for example {3,2,0,5,0,4,1,9,7,3}. What we want to do is to find the range of 5 consecutive elements with the "maximal minimum"... The solution in this example, would be this part {3,2,0,5,0,4,1,9,7,3} with 1 as the maximal minimum.

It's easy to do with O(n^2), but there must be a better way of doing this. What is it?

---

If you mean literally five consecutive elements, then you just need to keep a sorted window of the source array. Say you have: {3,2,0,5,0,1,0,4,1,9,7,3}

First, you get five elements and sort'em:

{3,2,0,5,0, 1,0,1,9,7,3}
{0,0,2,3,5} - sorted.

Here the minimum is the first element of the sorted sequence.

Then you need do advance it one step to the right, you see the new element 1 and the old one 3, you need to find and replace 3 with 1 and then return the array to the sorted state. You actually don't need to run a sorting algorithm on it, but you can as there is just one element that is in the wrong place (1 in this example). But even bubble sort will do it in linear time here.

{3,2,0,5,0,1, 0,4,1,9,7,3}
{0,0,1,2,5}

Then the new minimum is again the first element.

Then again and again you advance and compare first elements of the sorted sequence to the minimum and remember it and the subsequence.

Time complexity is O(n).

---

Can't you use some circular buffer of 5 elements, run over the array and add the newest element to the buffer (thereby replacing the oldest element) and searching for the lowest number in the buffer? Keep a variable with the offset into the array that gave the highest minimum.

That would seem to be O(n * 5*log(5)) = O(n), I believe.

Edit: I see unkulunkulu proposed exactly the same as me in more detail :).

---

Using a balanced binary search tree indtead of a linear buffer, it is trivial to get complexity O(n log m).

---

You can do it in O(n) for arbitrary k-consecutive elements as well. Use a deque.

For each element x:

pop elements from the back of the deque that are larger than x
if the front of the deque is more than k positions old, discard it
push x at the end of the deque

at each step, the front of the deque will give you the minimum of your
current k-element window. Compare it with your global maximum and update if needed.

Since each element gets pushed and popped from the deque at most once, this is O(n).

The deque data structure can either be implemented with an array the size of your initial sequence, obtaining O(n) memory usage, or with a linked list that actually deletes the needed elements from memory, obtaining O(k) memory usage.