Encontrar el máximo para cada ventana de tamaño k en una matriz

Dado un conjunto de tamaños nyk, ¿cómo se encuentra el máximo para cada subcampo contiguo de tamaño k?

Por ejemplo

arr = 1 5 2 6 3 1 24 7 k = 3 ans = 5 6 6 6 24 24 

Estaba pensando en tener una matriz de tamaño k y cada paso desaloja el último elemento y agrega el nuevo elemento y encuentra el máximo entre ellos. Esto lleva a un tiempo de ejecución de O (nk). ¿Hay una mejor manera de hacer esto?

Necesita una estructura de datos rápida que pueda agregar, eliminar y consultar el elemento máximo en menos de O (n) tiempo (puede usar una matriz si O (n) u O (nlogn) son aceptables). Puede usar un montón, un árbol de búsqueda binaria equilibrado, una lista de omisiones o cualquier otra estructura de datos ordenados que realice estas operaciones en O (log (n)).

La buena noticia es que la mayoría de los idiomas populares tienen implementada una estructura de datos ordenada que admite estas operaciones por usted. C ++ tiene std::set y std::multiset (probablemente necesite el último) y Java tiene TreeSet .

Has oído hablar de hacerlo en O (n) usando dequeue.

Bueno, ese es un algoritmo bien conocido para hacer esta pregunta en O (n).

El método que estoy diciendo es bastante simple y requiere una Progtwigción Dinámica y tiene una complejidad de tiempo O (n).

 Your Sample Input: n=10 , W = 3 10 3 1 -2 5 6 0 9 8 -1 2 0 Answer = 5 6 6 9 9 9 8 2 

Concepto: Progtwigción dinámica

Algoritmo:

  1. N es el número de elementos en una matriz y W es el tamaño de la ventana. Entonces, número de ventana = N-W + 1
  2. Ahora divide la matriz en bloques de W comenzando desde el índice 1.

    Aquí divide en bloques de tamaño ‘W’ = 3. Para su entrada de muestra:

    bloques divididos

  3. Hemos dividido en bloques porque calcularemos el máximo en 2 formas A.) atravesando de izquierda a derecha B.) atravesando de derecha a izquierda. pero cómo ??

  4. En primer lugar, atravesando de izquierda a derecha. Para cada elemento ai en bloque, encontraremos el máximo hasta ese elemento ai comenzando desde el START de Block hasta el END de ese bloque. Entonces aquí,

    LR

  5. En segundo lugar, atravesando de derecha a izquierda. Para cada elemento 'ai' en el bloque, encontraremos el máximo hasta que ese elemento 'ai' comience desde el final del bloque hasta el inicio de ese bloque. Entonces aquí,

    RL

  6. Ahora tenemos que encontrar el máximo para cada subcampo o ventana de tamaño ‘W’. Entonces, comenzando desde el índice = 1 hasta el índice = N-W + 1.

    max_val[index] = max(RL[index], LR[index+w-1]);

    LR + RL

      for index=1: max_val[1] = max(RL[1],LR[3]) = max(5,5)= 5 

Simultáneamente, para todo el índice i , (i<=(n-k+1)) , el valor en RL[i] y LR[i+w-1] se comparan y el máximo entre esos dos es la respuesta para ese subcampo.

Así que respuesta final: 5 6 6 9 9 9 8 2

Complejidad del tiempo: O (n)

Código de implementación:

 // Shashank Jain #include  #include  #include  #include  #define LIM 100001 using namespace std; int arr[LIM]; // Input Array int LR[LIM]; // maximum from Left to Right int RL[LIM]; // maximum from Right to left int max_val[LIM]; // number of subarrays(windows) will be n-k+1 int main(){ int n, w, i, k; // 'n' is number of elements in array // 'w' is Window's Size cin >> n >> w; k = n - w + 1; // 'K' is number of Windows for(i = 1; i <= n; i++) cin >> arr[i]; for(i = 1; i <= n; i++){ // for maximum Left to Right if(i % w == 1) // that means START of a block LR[i] = arr[i]; else LR[i] = max(LR[i - 1], arr[i]); } for(i = n; i >= 1; i--){ // for maximum Right to Left if(i == n) // Maybe the last block is not of size 'W'. RL[i] = arr[i]; else if(i % w == 0) // that means END of a block RL[i] = arr[i]; else RL[i] = max(RL[i+1], arr[i]); } for(i = 1; i <= k; i++) // maximum max_val[i] = max(RL[i], LR[i + w - 1]); for(i = 1; i <= k ; i++) cout << max_val[i] << " "; cout << endl; return 0; } 

Ejecutando Code Link


Intentaré probar: (por @ johnchen902)

Si k % w != 1 ( k no es el comienzo de un bloque)

 Let k* = The begin of block containing k ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1]) = max( max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k*]), max( arr[k*], arr[k* + 1], arr[k* + 2], ..., arr[k + w - 1]) ) = max( RL[k], LR[k+w-1] ) 

De lo contrario ( k es el comienzo de un bloque)

 ans[k] = max( arr[k], arr[k + 1], arr[k + 2], ..., arr[k + w - 1]) = RL[k] = LR[k+w-1] = max( RL[k], LR[k+w-1] ) 

El enfoque de progtwigción dinámica es muy bien explicado por Shashank Jain. Me gustaría explicar cómo hacer lo mismo con dequeue. La clave es mantener el elemento máximo en la parte superior de la cola (para una ventana) y descartar los elementos inútiles, y también tenemos que descartar los elementos que están fuera del índice de la ventana actual.
elementos inútiles = Si el elemento actual es mayor que el último elemento de la cola que el último elemento de la cola es inútil.
Nota: Estamos almacenando el índice en cola, no el elemento en sí. Será más claro desde el código mismo.
1. Si el elemento actual es mayor que el último elemento de la cola, el último elemento de la cola es inútil. Necesitamos eliminar ese último elemento. (y siga eliminando hasta que el último elemento de la cola sea más pequeño que el elemento actual).
2. Si if current_index – k> = q.front () eso significa que estamos saliendo de la ventana, entonces necesitamos eliminar el elemento del frente de la cola.

 vector max_sub_deque(vector &A,int k) { deque q; for(int i=0;i= A[q.back()]) q.pop_back(); q.push_back(i); } vector res; for(int i=k;i= A[q.back()] ) q.pop_back(); while(!q.empty() && q.front() <= ik) q.pop_front(); q.push_back(i); } res.push_back(A[q.front()]); return res; } 

Dado que cada elemento se pone en cola y se quita de la cola casi a la primera vez, la complejidad es
O (n + n) = O (2n) = O (n).
Y el tamaño de la cola no puede exceder el límite k. entonces la complejidad del espacio = O (k).

Una solución de O (n) tiempo es posible combinando las dos preguntas clásicas de la entrevista:

  • Crea una estructura de datos de stack (llamada MaxStack) que admite push, pop y max en O (1) tiempo.

    Esto se puede hacer usando dos stacks, la segunda contiene el mínimo visto hasta ahora.

  • Modele una cola con una stack.

    Esto puede hacerse usando dos stacks. Enqueues entran en una stack, y los deque provienen de la otra.

Para este problema, básicamente necesitamos una cola, que admita enqueue, dequeue y max en O (1) (tiempo amortizado).

Combinamos los dos anteriores, modelando una cola con dos MaxStacks.

Para resolver la pregunta, ponemos en cola k elementos, consultamos el máximo, dequeue, enqueue k + 1 ° elemento, consultamos el máximo, etc. Esto le dará el máximo para cada sub-matriz de tamaño k.

Creo que hay otras soluciones también.

1)

Creo que la idea de cola puede simplificarse. Mantenemos una cola y un máximo para cada k. Encolamos un nuevo elemento y dequeuimos todos los elementos que no son mayores que el nuevo elemento.

2) Mantenga dos matrices nuevas que mantengan el máximo de funcionamiento para cada bloque de k, una matriz para una dirección (de izquierda a derecha / de derecha a izquierda).

3) Usar un martillo: preprocesar en el tiempo O (n) para consultas de rango máximo.

La 1) solución anterior podría ser la más óptima.

Usando un montón (o árbol), deberías poder hacerlo en O(n * log(k)) . No estoy seguro de si esto sería realmente mejor.

Aquí está la implementación de java

 public static Integer[] maxsInEveryWindows(int[] arr, int k) { Deque deque = new ArrayDeque(); /* Process first k (or first window) elements of array */ for (int i = 0; i < k; i++) { // For very element, the previous smaller elements are useless so // remove them from deque while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) { deque.removeLast(); // Remove from rear } // Add new element at rear of queue deque.addLast(i); } List result = new ArrayList(); // Process rest of the elements, ie, from arr[k] to arr[n-1] for (int i = k; i < arr.length; i++) { // The element at the front of the queue is the largest element of // previous window, so add to result. result.add(arr[deque.getFirst()]); // Remove all elements smaller than the currently // being added element (remove useless elements) while (!deque.isEmpty() && arr[i] >= arr[deque.peekLast()]) { deque.removeLast(); } // Remove the elements which are out of this window while (!deque.isEmpty() && deque.getFirst() <= i - k) { deque.removeFirst(); } // Add current element at the rear of deque deque.addLast(i); } // Print the maximum element of last window result.add(arr[deque.getFirst()]); return result.toArray(new Integer[0]); } 

Aquí está el caso de prueba correspondiente

 @Test public void maxsInWindowsOfSizeKTest() { Integer[] result = ArrayUtils.maxsInEveryWindows(new int[]{1, 2, 3, 1, 4, 5, 2, 3, 6}, 3); assertThat(result, equalTo(new Integer[]{3, 3, 4, 5, 5, 5, 6})); result = ArrayUtils.maxsInEveryWindows(new int[]{8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, 4); assertThat(result, equalTo(new Integer[]{10, 10, 10, 15, 15, 90, 90})); } 

Usando el montón de Fibonacci, puedes hacerlo en O(n + (nk) log k) , que es igual a O(n log k) para k pequeña, para k cerca de n esto se convierte en O(n) .

El algoritmo: de hecho, necesitas:

  • n inserciones en el montón
  • deleciones nk
  • nk Findmax de

¿Cuánto cuestan estas operaciones en montones de Fibonacci ? Insert y findmax es O(1) amortizado, la eliminación es O(log n) amortizado. Entonces tenemos

 O(n + (nk) log k + (nk)) = O(n + (nk) log k) 

Lo siento, esto debería haber sido un comentario, pero no puedo comentar por ahora. @leo y @Clay Goddard Pueden ahorrarse el volver a calcular el máximo storing both maximum and 2nd maximum of the window in the beginning (el segundo máximo será el máximo solo si hay dos máximos en la ventana inicial). Si el máximo se desliza fuera de la ventana, aún tiene el siguiente mejor candidato para comparar con la nueva entrada. Así que obtienes O(n) , de lo contrario, si permites volver a calcular todo, el peor de los casos sería O (nk), k es el tamaño de la ventana.

 class MaxFinder { // finds the max and its index static int[] findMaxByIteration(int arr[], int start, int end) { int max, max_ndx; max = arr[start]; max_ndx = start; for (int i=start; i max) { max = arr[i]; max_ndx = i; } } int result[] = {max, max_ndx}; return result; } // optimized to skip iteration, when previous windows max element // is present in current window static void optimizedPrintKMax(int arr[], int n, int k) { int i, j, max, max_ndx; // for first window - find by iteration. int result[] = findMaxByIteration(arr, 0, k); System.out.printf("%d ", result[0]); max = result[0]; max_ndx = result[1]; for (j=1; j <= (nk); j++) { // if previous max has fallen out of current window, iterate and find if (max_ndx < j) { result = findMaxByIteration(arr, j, j+k); max = result[0]; max_ndx = result[1]; } // optimized path, just compare max with new_elem that has come into the window else { int new_elem_ndx = j + (k-1); if (arr[new_elem_ndx] > max) { max = arr[new_elem_ndx]; max_ndx = new_elem_ndx; } } System.out.printf("%d ", max); } } public static void main(String[] args) { int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; //int arr[] = {1,5,2,6,3,1,24,7}; int n = arr.length; int k = 3; optimizedPrintKMax(arr, n, k); } } 
 package com; public class SlidingWindow { public static void main(String[] args) { int[] array = { 1, 5, 2, 6, 3, 1, 24, 7 }; int slide = 3;//say List result = new ArrayList(); for (int i = 0; i < array.length - (slide-1); i++) { result.add(getMax(array, i, slide)); } System.out.println("MaxList->>>>" + result.toString()); } private static Integer getMax(int[] array, int i, int slide) { List intermediate = new ArrayList(); System.out.println("Initial::" + intermediate.size()); while (intermediate.size() < slide) { intermediate.add(array[i]); i++; } Collections.sort(intermediate); return intermediate.get(slide - 1); } } 

Aquí está la solución en O (n) complejidad de tiempo con deque auxiliar

 public class TestSlidingWindow { public static void main(String[] args) { int[] arr = { 1, 5, 7, 2, 1, 3, 4 }; int k = 3; printMaxInSlidingWindow(arr, k); } public static void printMaxInSlidingWindow(int[] arr, int k) { Deque queue = new ArrayDeque(); Deque auxQueue = new ArrayDeque(); int[] resultArr = new int[(arr.length - k) + 1]; int maxElement = 0; int j = 0; for (int i = 0; i < arr.length; i++) { queue.add(arr[i]); if (arr[i] > maxElement) { maxElement = arr[i]; } /** we need to maintain the auxiliary deque to maintain max element in case max element is removed. We add the element to deque straight away if subsequent element is less than the last element (as there is a probability if last element is removed this element can be max element) otherwise remove all lesser element then insert current element **/ if (auxQueue.size() > 0) { if (arr[i] < auxQueue.peek()) { auxQueue.push(arr[i]); } else { while (auxQueue.size() > 0 && (arr[i] > auxQueue.peek())) { auxQueue.pollLast(); } auxQueue.push(arr[i]); } }else { auxQueue.push(arr[i]); } if (queue.size() > 3) { int removedEl = queue.removeFirst(); if (maxElement == removedEl) { maxElement = auxQueue.pollFirst(); } } if (queue.size() == 3) { resultArr[j++] = maxElement; } } for (int i = 0; i < resultArr.length; i++) { System.out.println(resultArr[i]); } } } 

Solo tenga en cuenta que solo tiene que encontrar en la nueva ventana si: * El nuevo elemento en la ventana es más pequeño que el anterior (si es más grande, seguro que este). O * El elemento que acaba de salir de la ventana era el actual más grande.

En este caso, vuelva a escanear la ventana.

Una solución de trabajo completa en Amortized Constant O (1) Complexity. https://github.com/varoonverma/code-challenge.git

He creado una solución simple, que no necesita cosas sofisticadas. La idea es hacer un seguimiento del máximo de la ventana anterior y actualizarlo solo cuando sea necesario.

 void printKMax(int arr[], int n, int k) { int max = arr[0]; // find max of initial k elements. for (int i = 1; i < k; i++) { if (arr[i] > max) max = arr[i]; } printf("%d ", max); for (int i = k; i < n; i++) { if (arr[i] > max) // Compare it with just next element. max = arr[i]; printf("%d ", max); } } 

No entendí, es su problema con este código, por qué no le importó a nadie. Complejidad del tiempo => O (n)

para qué tan grande k? para k de tamaño razonable. puede crear búferes de tamaño k k y simplemente iterar sobre la matriz manteniendo un registro de los punteros de elemento máximo en los búferes; no necesita estructuras de datos y es O (n) k ^ 2 preasignación.

Compara los primeros k elementos y encuentra el máximo, este es tu primer número

luego compara el siguiente elemento con el máximo anterior. Si el siguiente elemento es más grande, ese es el máximo de la submatriz siguiente, si es igual o más pequeño, el máximo para esa matriz secundaria es el mismo

luego pasa al siguiente número

 max(1 5 2) = 5 max(5 6) = 6 max(6 6) = 6 ... and so on max(3 24) = 24 max(24 7) = 24 

Es solo un poco mejor que tu respuesta