Saltar al contenido

Solicitudes en la última ventana

Fácil#queue#sliding-window~15 min

La misión

Problema

Un servicio registra en milisegundos la hora de llegada de cada solicitud, y los tiempos llegan en orden no decreciente. Para cada solicitud, indica cuántas solicitudes, incluida ella misma, llegaron durante los últimos w milisegundos, es decir, en un tiempo estrictamente mayor que su propio tiempo menos w. Devuelve un conteo por solicitud.

Ejemplos

Input:  times = [0, 400, 900, 1000, 1400], w = 1000
Output: [1, 2, 3, 3, 3]
Por qué: en 1000, la solicitud del tiempo 0 tiene exactamente w de antigüedad y ya no cuenta
Input:  times = [5, 5, 5], w = 1
Output: [1, 2, 3]
Por qué: los tiempos iguales caen todos dentro de la misma ventana
Input:  times = [], w = 50
Output: []
Por qué: caso límite: no hay solicitudes

Pistas

0 / 3

Tiempo objetivo
O(n)
Espacio objetivo
O(n)

Restricciones

  • times are in non-decreasing order

¿Lo que te frena es la idea y no el código? Fundamentos de la cola lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio