Solicitudes en la última ventana
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
Una vez que una solicitud es demasiado vieja para una llegada, también lo es para todas las llegadas posteriores, porque los tiempos nunca bajan.
Las solicitudes viejas salen por el frente y las nuevas entran por el final, que es exactamente primero en entrar, primero en salir.
Mantén una cola de tiempos. Para cada llegada, agrega su tiempo al final y después quita tiempos del frente mientras el tiempo del frente sea como máximo el tiempo de llegada menos w. La longitud de la cola es la respuesta para esa llegada.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- times are in non-decreasing order
Solución
Como los tiempos nunca bajan, las solicitudes expiran en el mismo orden en que llegaron, así que las que siguen dentro de la ventana siempre forman un tramo al frente de una cola (queue). Cada llegada entra por el final, y los tiempos vencidos salen por el frente hasta que el más antiguo que queda es lo bastante reciente. Cada tiempo se agrega una vez y se quita como máximo una vez, así que el trabajo total es lineal incluso cuando una sola llegada quita muchos. El tiempo es O(n) y el espacio es O(n), que se alcanza cuando todas las solicitudes caen dentro de una misma ventana.
from collections import deque
def recent_counts(times, w):
window, out = deque(), []
for t in times:
window.append(t)
while window[0] <= t - w: # too old now, and for every later arrival
window.popleft()
out.append(len(window))
return out
print(recent_counts([0, 400, 900, 1000, 1400], 1000)) # -> [1, 2, 3, 3, 3]
print(recent_counts([5, 5, 5], 1)) # -> [1, 2, 3]
print(recent_counts([], 50)) # -> []¿Lo que te frena es la idea y no el código? Fundamentos de la cola lo explica.