Entrevista técnica: ¿Cómo resolver el máximo en una ventana deslizante con una deque monotónica?

Problema y escenarios de aplicación

Dado un arreglo de enteros nums y un tamaño de ventana k, la primera ventana cubre los índices desde 0 hasta k - 1. Mueve la ventana una posición a la derecha a la vez y devuelve el máximo de cada ventana. Las restricciones son 1 <= nums.length <= 100000 y 1 <= k <= nums.length. Por ejemplo:

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
result = [3, 3, 5, 5, 6, 7]

El objetivo es tiempo O(n) y espacio auxiliar O(k), excluyendo el arreglo de salida. El problema estándar garantiza un arreglo no vacío y un k válido. Si una API de producción debe aceptar un arreglo vacío o un k inválido, define el valor de retorno o la excepción por separado en lugar de mezclar un comportamiento no especificado en la demostración del algoritmo.

Múltiples recursos de preparación para entrevistas en chino e inglés publicados en 2026 todavía utilizan el Máximo en Ventana Deslizante como un ejercicio directo de deque monotónica y piden a los candidatos que expliquen el elemento frontal, los índices expirados, la expulsión trasera y la complejidad amortizada. Una solución pública en chino publicada en 2026 también compara los enfoques de fuerza bruta y deque. La habilidad central es el razonamiento general sobre algoritmos y estructuras de datos, por lo que la categoría correcta es coding; el ejemplo en TypeScript no lo convierte en una pregunta de frontend.

Qué evalúa el entrevistador

Primero, ¿puedes reconocer la estructura: un elemento entra y otro sale en cada movimiento, mientras que un valor extremo debe permanecer disponible? La fuerza bruta vuelve a escanear los k - 1 elementos compartidos por ventanas adyacentes. Una deque monotónica mantiene únicamente los índices que aún pueden convertirse en el máximo actual o futuro.

Segundo, ¿puedes explicar por qué la deque almacena índices en lugar de solo valores? La expiración depende de la posición, y valores iguales pueden provenir de diferentes posiciones. Sin índices, no puedes determinar de manera confiable si el máximo al frente ha salido de la ventana.

Tercero, ¿puedes demostrar que un elemento trasero puede eliminarse permanentemente? Si j < i y nums[j] <= nums[i], el elemento más nuevo es al menos tan grande y expira más tarde. Siempre que ambos estén en una ventana, el elemento más antiguo no puede ganar. Este es un argumento de dominancia, no simplemente una forma de hacer que la deque parezca ordenada.

Finalmente, la complejidad requiere un análisis amortizado. Una sola iteración puede eliminar varios índices, por lo que una iteración individual no es estrictamente O(1). Sin embargo, cada índice entra una vez y sale a lo sumo una vez de cualquiera de los dos extremos, por lo que todas las operaciones de la deque en conjunto toman tiempo O(n).

Preguntas aclaratorias antes de responder

• ¿El tamaño de la ventana es fijo? Está fijado en k; una ventana variable requeriría una regla de expiración y un contrato de consulta revisados.
• ¿Puede el arreglo estar vacío? Las restricciones estándar lo excluyen; una API extendida debería devolver explícitamente un arreglo vacío o rechazar la entrada.
• ¿Se garantiza que k es válido? El enunciado indica que sí; la implementación de muestra aún lo valida en tiempo de ejecución para evitar longitudes inválidas o accesos fuera de límites.
• ¿Pueden los valores repetirse o ser negativos? Sí. El algoritmo depende únicamente de comparaciones e índices, no de la positividad ni de la unicidad.
• ¿En valores iguales se debe conservar el índice más nuevo o el más antiguo? Ambos producen los máximos correctos. Esta solución elimina el valor igual más antiguo y conserva el índice que expira más tarde.
• ¿El espacio auxiliar debe ser estrictamente O(k)? Sí. Un arreglo de JavaScript que solo avanza un puntero de inicio sin liberar los espacios antiguos puede retener O(n) de almacenamiento; esta solución utiliza un búfer circular de capacidad k.
• ¿Devolvemos valores o índices de los máximos? El problema principal devuelve valores. Si se requieren índices, devuelve el índice frontal y define la regla de desempate para máximos duplicados.
• ¿Se puede modificar la entrada? No. La implementación solo lee nums.

Esquema de respuesta de 30 segundos

“Mantendré los índices candidatos en una deque. Los índices aumentan de adelante hacia atrás, mientras que sus valores disminuyen estrictamente. En el índice i, primero elimino los índices expirados del frente. Luego elimino los índices de la parte trasera mientras sus valores sean menores o iguales a nums[i], porque el nuevo elemento es al menos tan grande y expira más tarde. Después de insertar i, el valor del frente es la respuesta una vez que existe la primera ventana completa. Cada índice se inserta una vez y se elimina a lo sumo una vez, por lo que el tiempo total es O(n). La deque contiene como máximo k índices, lo que da un espacio auxiliar de O(k)”.

Análisis detallado paso a paso

Paso 1: Usar enfoques de referencia para ubicar el trabajo repetido.

Cuando tanto n como k se acercan a 100000, la fuerza bruta puede realizar aproximadamente 10^10 comparaciones. Un montículo es una respuesta intermedia útil, pero mantiene la prioridad entre todas las entradas. Este problema solo lee el máximo, por lo que un candidato más antiguo dominado por una entrada más nueva no tiene valor futuro.

Paso 2: Formular la regla de dominancia con precisión.

Supongamos que j < i y nums[j] <= nums[i]. En cada ventana futura que contenga ambos índices, el valor en j no puede exceder el valor en i. A medida que la ventana se mueve hacia la derecha, j también expira antes que i. Por lo tanto, desde el momento en que llega i, j nunca más podrá convertirse en el máximo de una ventana y puede ser eliminado permanentemente del conjunto de candidatos.

Usar menor o igual en la condición de eliminación conserva únicamente el índice más reciente para valores iguales y hace que los valores de la deque sean estrictamente decrecientes. Eliminar solo valores estrictamente menores también es correcto, pero entonces los valores son meramente no crecientes y permanecen múltiples candidatos iguales. La demostración y el código deben utilizar la misma estrategia.

Paso 3: Mantener cuatro invariantes verificables.

Después de procesar el índice i:

1. Los índices en la deque aumentan estrictamente y siguen el orden de llegada.
2. Cada índice almacenado se encuentra en el rango actual [i - k + 1, i].
3. Los valores correspondientes del arreglo disminuyen estrictamente de adelante hacia atrás.
4. Cada índice eliminado de la ventana actual tiene un candidato posterior y no menor que permanece a lo largo de su cadena de dominancia.

Las primeras tres propiedades hacen que el frente sea el candidato retenido más grande. La cuarta demuestra que ningún elemento descartado podría haber sido el verdadero máximo. Juntas, establecen que el frente representa a toda la ventana, no simplemente al elemento más grande dentro de la deque.

Paso 4: Implementar una deque circular que realmente use espacio O(k).

export function maxSlidingWindow(
  nums: readonly number[],
  k: number,
): number[] {
  if (!Number.isInteger(k) || k < 1 || k > nums.length) {
    throw new RangeError("k must be an integer between 1 and nums.length");
  }

  const deque = new Int32Array(k);
  let head = 0;
  let size = 0;
  const result: number[] = [];

  for (let i = 0; i < nums.length; i += 1) {
    while (size > 0 && deque[head] <= i - k) {
      head = (head + 1) % k;
      size -= 1;
    }

    while (size > 0) {
      const back = (head + size - 1) % k;
      if (nums[deque[back]] > nums[i]) break;
      size -= 1;
    }

    deque[(head + size) % k] = i;
    size += 1;

    if (i >= k - 1) {
      result.push(nums[deque[head]]);
    }
  }

  return result;
}

El búfer circular tiene exactamente k ranuras. Las entradas expiradas se eliminan antes de cada inserción, por lo que la ventana actual contiene como máximo k - 1 índices válidos antes de escribir el nuevo; la inserción no puede sobrescribir el frente. Int32Array puede almacenar índices hasta el máximo indicado de 100000. Si una variante permite índices más allá del rango de 32 bits, utiliza un arreglo numérico regular o revisa el contrato de entrada.

Paso 5: Demostrar que cada valor reportado es el verdadero máximo de la ventana.

La deque comienza vacía, por lo que se cumplen todos los invariantes. Cuando llega un nuevo índice, la eliminación frontal descarta únicamente elementos fuera de la ventana actual. La eliminación trasera aplica la regla de dominancia: cada elemento eliminado se reemplaza por el índice más nuevo y no menor i. Insertar i preserva los índices crecientes y los valores estrictamente decrecientes.

La primera ventana completa existe en i = k - 1. A partir de ese momento, el frente siempre está dentro de la ventana. Los valores estrictamente decrecientes en la deque lo hacen mayor que cualquier otro candidato retenido, mientras que las cadenas de dominancia aseguran que cada elemento no retenido no sea mayor que algún candidato retenido. Por lo tanto, nums[deque[head]] es el máximo actual. La inducción sobre todo i demuestra que todas las salidas n - k + 1 son correctas.

Paso 6: Rastrear duplicados y el límite de expiración.

Para el ejemplo, cada entrada a continuación es index:value:

i=0  [0:1]                  no full window yet
i=1  [1:3]                  3 dominates 1
i=2  [1:3, 2:-1]            output 3
i=3  [1:3, 2:-1, 3:-3]      output 3
i=4  [4:5]                  1 expires; 5 dominates -1 and -3; output 5
i=5  [4:5, 5:3]             output 5
i=6  [6:6]                  6 dominates 5 and 3; output 6
i=7  [7:7]                  7 dominates 6; output 7

Para [4, 4, 4] con k = 2, el segundo 4 elimina al primero, y el tercer 4 elimina al segundo. La deque siempre contiene el índice más reciente, mientras que ambas ventanas siguen retornando 4. Este caso verifica la condición de valor igual y expone por qué almacenar solo valores no permite rastrear la expiración correctamente.

Paso 7: Indicar con precisión la complejidad amortizada.

Los dos bucles while no multiplican la complejidad a O(nk). Cada índice se inserta una vez y nunca regresa tras su eliminación, por lo que todas las eliminaciones frontales y traseras juntas ocurren a lo sumo n veces. El tiempo total es O(n). La deque circular almacena como máximo k índices, por lo que el espacio auxiliar es O(k). La salida tiene n - k + 1 entradas y normalmente se excluye del análisis del espacio auxiliar.

Paso 8: Usar un oráculo ingenuo para pruebas diferenciales.

Los casos fijos deben cubrir k = 1, k = n, valores todos iguales, arreglos estrictamente crecientes y decrecientes, valores todos negativos y el ejemplo mixto estándar. Un arreglo vacío y k = 0 son entradas inválidas y deben lanzar RangeError. Luego genera arreglos aleatorios cortos y un k válido aleatorio, y compara cada salida con una implementación ingenua que escanee cada ventana. La verificación aleatoria debe comprobar tanto la longitud del resultado como el valor de cada ventana.

Para un n muy pequeño o una sola ventana, el escaneo por fuerza bruta es más corto y fácil de revisar. Si el lenguaje proporciona una deque confiable, prefiere ese contenedor estándar. El búfer circular se presenta aquí para que el límite de almacenamiento físico de la implementación en TypeScript coincida con su análisis de O(k).

Respuesta de muestra sólida

“La fuerza bruta escanea k elementos para cada ventana, lo que representa O(nk) en el peor de los casos. Yo mantendría una deque monotónica de índices. Los índices aumentan en orden de llegada, mientras que sus valores disminuyen estrictamente de adelante hacia atrás.

En el índice i, primero elimino cada índice frontal menor o igual a i - k, porque ya ha expirado. Luego elimino los índices de la parte trasera mientras sus valores sean menores o iguales a nums[i]. El nuevo elemento es al menos tan grande y sale de la ventana más tarde, por lo que esos elementos más antiguos nunca podrán volver a ser un máximo. Inserto i, y una vez que i >= k - 1, el frente proporciona el máximo actual.

La corrección se deriva de dos hechos: las eliminaciones frontales están fuera de la ventana, y cada eliminación trasera tiene un reemplazo más nuevo y no menor que sobrevive más tiempo. Dado que los valores retenidos decrecen, el candidato restante más grande está en el frente. Cada índice entra una vez y sale a lo sumo una vez, por lo que el tiempo total es O(n). La deque almacena como máximo k índices, lo que da un espacio auxiliar de O(k). Yo probaría con k = 1, k = n, valores duplicados, arreglos monótonos y números negativos, y luego compararía casos aleatorios frente a un oráculo de fuerza bruta”.

Errores comunes

• Almacenar solo valores en la deque → Los valores iguales no se pueden distinguir al expirar → Almacenar índices y leer los valores del arreglo.
• Mantener valores decrecientes pero nunca eliminar frentes expirados → Un máximo antiguo sigue apareciendo tras salir de la ventana → Limpiar el frente usando i - k en cada iteración.
• Usar < i - k como prueba de expiración → El índice igual a i - k ya está a la izquierda de la ventana → Usar menor o igual.
• Llamar O(nk) a los bucles anidados de while → Un índice no puede eliminarse repetidamente → Usar el hecho de que cada índice entra y sale a lo sumo una vez.
• Usar shift() y afirmar eliminación en tiempo constante → JavaScript puede desplazar elementos del arreglo en una eliminación frontal → Usar una deque estándar, un puntero de inicio o un búfer circular.
• Avanzar un puntero de inicio sin liberar almacenamiento y afirmar espacio O(k) → El arreglo subyacente aún puede crecer hasta O(n) → Usar almacenamiento circular con capacidad fija de k.
• Desajuste entre la regla de valores iguales y la demostración → Se mezclan invariantes estrictamente decrecientes y no crecientes → Declarar que esta solución elimina valores más antiguos con menor o igual.
• Poner solo valores en un montículo → La eliminación perezosa aún no puede identificar entradas expiradas → Un enfoque con montículo también debe almacenar índices.
• Probar únicamente el ejemplo estándar → Los errores de límite en k = 1, duplicados y arreglos decrecientes permanecen ocultos → Agregar límites fijos y un oráculo aleatorio.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Por qué es seguro eliminar un valor igual más antiguo?

El índice más nuevo tiene el mismo valor y necesariamente expira más tarde. En cada ventana que contenga a ambos, cualquiera de los dos índices suministra el mismo máximo. El más antiguo sale primero y no puede recuperar una oportunidad después de que el más nuevo expire. Conservar solo el índice más nuevo es, por lo tanto, seguro y acorta la deque.

Pregunta de seguimiento 2: ¿Qué pasa si el resultado debe incluir la primera aparición de cada máximo?

No elimines los valores iguales más antiguos. Elimina solo valores estrictamente menores de la parte trasera, haciendo que los valores de la deque sean no crecientes. El frente mantendrá entonces el máximo más temprano en la ventana actual. Si el resultado requiere la última aparición, conserva la eliminación con menor o igual de esta solución. La regla de desempate cambia, pero el límite O(n) se mantiene.

Pregunta de seguimiento 3: ¿Por qué no usar un montículo de máximos?

Un montículo es una solución rápida válida cuando almacena valores e índices y realiza eliminación perezosa. Las entradas expiradas que no están en la cima permanecen asignadas, por lo que un montículo binario ordinario puede crecer hasta un espacio de O(n) y toma un tiempo de O(n log n). Un montículo indexado con eliminación arbitraria puede lograr un tiempo de O(n log k) y un espacio de O(k), pero es más complejo. En una entrevista, el montículo puede ser una respuesta intermedia útil antes de optimizar a una deque monotónica.

Pregunta de seguimiento 4: ¿Qué pasa si cada ventana necesita tanto su máximo como su mínimo?

Mantén dos deques independientes: una con valores decrecientes para el máximo y otra con valores crecientes para el mínimo. Cada índice sigue entrando y saliendo de cada deque a lo sumo una vez, por lo que el tiempo total sigue siendo O(n) y el espacio auxiliar sigue siendo O(k).

Pregunta de seguimiento 5: ¿Qué pasa si el tamaño de la ventana cambia en cada consulta?

Si ambos límites todavía se mueven únicamente hacia la derecha, usa el límite izquierdo actual para eliminar índices expirados y la deque monotónica seguirá funcionando. Si la ventana puede expandirse hacia la izquierda, los candidatos que fueron descartados permanentemente pueden volver a entrar al rango y no pueden recuperarse. Utiliza un árbol balanceado, un árbol de segmentos o una estructura de consultas de máximo en rango fuera de línea según el patrón de actualización y consulta.

Pregunta de seguimiento 6: ¿Cómo procesarías un flujo infinito en línea?

Asigna un número de secuencia creciente a cada llegada, aplica los mismos pasos de expiración y eliminación trasera, y emite el valor del frente después del elemento número k y en cada llegada posterior. Almacena como máximo k índices y valores candidatos, de modo que la memoria sea independiente de la longitud total del flujo. Las llegadas fuera de orden requerirían adicionalmente una ventana de tiempo de evento, marcas de agua (watermarks) y una política de datos tardíos; eso queda fuera del modelo de arreglo ordenado de este problema.

Pregunta de seguimiento 7: ¿Cómo se extiende este patrón a la programación dinámica acotada?

Para una recurrencia donde el estado actual es igual a su propio costo más el máximo de los k estados anteriores, mantén una deque ordenada por el valor de DP. El frente suministra el máximo para la transición, mientras que la expiración aún depende del índice. El objetivo de comparación cambia de nums[i] a dp[i], pero la demostración sigue basándose en que un estado posterior y no menor domina a un estado más antiguo.