Si encuentras algo que no entiendes puedes dejarlo en la sección de comentarios y haremos todo lo necesario de ayudarte lo más rápido posible.
Solución:
En términos generales, una ventana deslizante es una sublista que se ejecuta sobre una colección subyacente. es decir, si tiene un array me gusta
[a b c d e f g h]
una ventana corrediza de tamaño 3 pasaría por encima como
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
Esto es útil si, por ejemplo, desea calcular un promedio móvil o si desea crear un conjunto de todos los pares adyacentes, etc.
La ventana deslizante es una técnica de resolución de problemas que involucran matrices/listas. Estos problemas son fáciles de resolver usando un enfoque de fuerza bruta en O(n^2) u O(n^3). Usando la técnica de la ‘ventana deslizante’, podemos reducir la complejidad del tiempo a O(n).
Gran artículo sobre esto está aquí: https://medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66
Entonces, lo primero que debe poder hacer es identificar un problema que use un paradigma de ventana deslizante. Afortunadamente, hay algunos obsequios comunes:
El problema implicará una estructura de datos ordenada e iterable como un array o un string
Estás buscando algún subrango en eso array/stringcomo el valor más largo, más corto o de destino.
Existe una solución aparentemente ingenua o de fuerza bruta que se ejecuta en O (N²), O (2 ^ N) o alguna otra complejidad de tiempo grande.
Pero el mayor obsequio es que lo que está buscando suele ser algún tipo de óptimo, como la secuencia más larga o la secuencia más corta de algo que satisface exactamente una condición dada.
Lo considero más una técnica que un algoritmo. Es una técnica que podría utilizarse en varios algoritmos.
Creo que la técnica se entiende mejor con el siguiente ejemplo. Imagina que tenemos esto array:
[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]
¿Cómo encontraríamos la mayor suma de cinco elementos consecutivos? Bueno, primero miraríamos 5, 7, 1, 4, 3 y ver que la suma es 20. Luego miraríamos el siguiente conjunto de cinco elementos consecutivos, que es 7, 1, 4, 3, 6. la suma de esos es 21. Esto es más que nuestra suma anterior, por lo que 7, 1, 4, 3, 6 actualmente es lo mejor que tenemos hasta ahora.
A ver si podemos mejorar. 1, 4, 3, 6, 2? No, eso suma 16. 4, 3, 6, 2, 9? Eso suma a 24, así que ahora esa es la mejor secuencia que tenemos. Ahora pasamos a la siguiente secuencia, 3, 6, 2, 9, 2. que uno suma 22que no supera nuestro actual mejor de 24. Y hemos llegado al final, así que hemos terminado.
La fuerza bruta de implementar esto en el código es la siguiente:
const getMaxSumOfFiveContiguousElements = (arr) =>
let maxSum = -Infinity;
let currSum;
for (let i = 0; i <= arr.length - 5; i++)
currSum = 0;
for (let j = i; j <= i + 5; j++)
currSum += arr[j];
maxSum = Math.max(maxSum, currSum);
return maxSum;
;
¿Cuál es la complejidad temporal de esto? Es O(n*k). El bucle exterior está pasando n - k + 1 artículos, pero cuando n es mucho más grande que kpodemos olvidarnos de la k + 1 parte y simplemente llámalo n elementos. Entonces el bucle interno está pasando k elementos, por lo que tenemos O(n*k). Intenta visualizarlo así:
¿Podemos reducir esto a solo O(n)? volvamos a esto array:
[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]
Primero obtenemos la suma de 5, 7, 1, 4, 3. Luego necesitamos la suma de 7, 1, 4, 3, 6. Visualícelo así, con una "ventana" que rodea cada grupo de cinco elementos.
¿Cuál es la diferencia entre la primera ventana y la segunda ventana? Bueno, la segunda ventana se deshizo del 5 a la izquierda, pero agregó un 6 a la derecha. Como sabemos que la suma de la primera ventana fue 20para obtener la suma de la segunda ventana, tomamos que 20resta el 5y agregue el 6 Llegar 21. En realidad, no tenemos que revisar cada elemento en la segunda ventana y sumarlos (7 + 1 + 4 + 3 + 6). Eso implicaría hacer un trabajo repetido e innecesario.
Aquí el enfoque de la ventana deslizante termina siendo dos operaciones en lugar de cinco, ya que k es 5. Eso no es una gran mejora, pero puedes imaginar que para más k (y más grande n) realmente ayuda.
Así es como funcionaría el código usando la técnica de ventana deslizante:
const getLargestSumOfFiveConsecutiveElements = (arr) =>
let currSum = getSum(arr, 0, 4);
let largestSum = currSum;
for (let i = 1; i <= arr.length - 5; i++)
currSum -= arr[i - 1]; // subtract element to the left of curr window
currSum += arr[i + 4]; // add last element in curr window
largestSum = Math.max(largestSum, currSum);
return largestSum;
;
const getSum = (arr, start, end) =>
let sum = 0;
for (let i = start; i <= end; i++)
sum += arr[i];
return sum;
;
Y esa es la esencia de la técnica de la ventana deslizante. En otros problemas, puede estar haciendo algo más complicado que obtener la suma de los elementos dentro de la ventana. O la ventana en sí puede tener un tamaño variable en lugar del tamaño fijo de cinco que vimos aquí. Pero esta aplicación básica de la técnica de la ventana deslizante debería darle una base a partir de la cual podría construir.
Más adelante puedes encontrar las interpretaciones de otros creadores, tú asimismo puedes insertar el tuyo si lo deseas.