Encontrar los locales $k$-máximo en secuencia $a_1, a_2, \ldots a_n$.

Question

Para dar secuencia de números $a_1, a_2, \ldots, a_n$ decimos que $a_i$ $k$ local máximo, si $i > k$ y $ai$ son el más grande de números $a{i - k}, a_{i-k+1}, \ldots, a_i$.

¿Cómo podemos encontrar todas las %#% máximos de #%-local en marcha tiempo $k$? Algoritmo toma entero $\mathcal{O}(n \log k)$y la secuencia $k$.

Answer 1

Inserte un salto lista $a_1,a_2,\ldots a_k$ a $L$.

Crear un $k$-tamaño array (llamado, decir, $A$) con punteros a los nodos de $a_1,a_2,\ldots a_k$ se almacenan en dentro de la lista de salto.

A continuación, $i\in {k+1,k+2,\ldots n}$:

1. Si $a_i\geq \max (L)$, luego informe $a_i$ como $k$-local máximo.
2. Eliminar el nodo indicado en $A[i \mod k]$ $L$.
3. Añadir $a_i$ $L$.
4. Set $A[i \mod k]$ a en el nodo recién creado.

Total tiempo de ejecución es $O(n\log k)$, $O(\log k)$ tarda cada iteración.