Ventana variable con dos punteros
Amplíe y reduzca la ventana hasta cumplir una condición
Ventana variable con dos punteros es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Cuando la ventana se adapta
Algunos problemas no fijan la longitud de la ventana. En su lugar, la ventana se expande y se contrae para mantener una condición verdadera, como que una suma permanezca por debajo de un límite.
Dos punteros, una ventana
Mantenga dos índices, left y right, que marquen los extremos de la ventana. El puntero right se expande mientras left queda atrás para reducirla cuando sea necesario.
left = 0
window = 0Expanda hacia la derecha
Recorra hacia la derecha todos los elementos e inclúyalo en la ventana. Actualice el estado acumulado, por ejemplo, añadiendo el nuevo valor a una suma.
for right in range(n):
window += a[right]Reduzca cuando sea necesario
Mientras la ventana viole la regla, mueva left hacia la derecha y elimine ese elemento. Así restablece la condición sin retroceder.
while window > limit:
window -= a[left]
left += 1Lea la ventana válida
Cuando termina el bucle interno, la ventana de left a right es válida. Su longitud es right menos left más uno, y ya puede utilizarla.
length = right - left + 1Registre su mejor resultado
Actualice la respuesta con esta ventana válida, que a menudo será la más larga encontrada. Hágalo en cada iteración para no omitir ninguna.
best = max(best, right - left + 1)Por qué es lineal
Cada puntero solo avanza hacia delante, nunca retrocede. left y right avanzan juntos como máximo n pasos, por lo que todo el recorrido cuesta O(n).
El requisito de monotonía
Esto funciona cuando ampliar la ventana solo hace que la condición sea más difícil de satisfacer. Ese comportamiento monótono es lo que permite que left nunca retroceda.
Más larga frente a más corta
Para encontrar la ventana válida más corta, redúzcala mientras la regla siga cumpliéndose y registre el resultado antes de detenerse. La mecánica de los punteros no cambia.
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1Evite las ventanas vacías
Si al reducir la ventana esta puede quedar vacía, compruebe que left supere a right. Confirme también que realmente se encontró una respuesta antes de devolverla.
Identifique el patrón
Elija una ventana variable cuando el problema pida el tramo contiguo más largo o más corto que cumpla una condición sobre sus elementos.
Comprobación rápida
Ejecuta una ventana variable con dos punteros sobre un arreglo de tamaño n.
Resumen
Expanda right para incluir elementos, reduzca left mientras se incumpla la regla y registre cada ventana válida. Los punteros que solo avanzan mantienen el costo en O(n). ✅
Preguntas frecuentes
¿La lección «Ventana variable con dos punteros» es gratis?
Sí — el texto completo de «Ventana variable con dos punteros» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Ventana variable con dos punteros»?
Amplíe y reduzca la ventana hasta cumplir una condición Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Ventana variable con dos punteros»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Sumas de ventanas de tamaño fijo
- Ventana variable con dos punteros
- Subcadena más larga sin repeticiones
- Cuente ventanas que cumplen una regla