Pular para o conteúdo

Requisições na última janela

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

A missão

Problema

Um serviço registra o horário de chegada de cada requisição em milissegundos, e os horários vêm em ordem não decrescente. Para cada requisição, informe quantas requisições, incluindo ela mesma, chegaram durante os últimos w milissegundos, ou seja, em um horário estritamente maior que o horário dela menos w. Retorne uma contagem por requisição.

Exemplos

Input:  times = [0, 400, 900, 1000, 1400], w = 1000
Output: [1, 2, 3, 3, 3]
Por quê: em 1000, a requisição do horário 0 tem exatamente w de idade e deixa de contar
Input:  times = [5, 5, 5], w = 1
Output: [1, 2, 3]
Por quê: horários iguais caem todos na mesma janela
Input:  times = [], w = 50
Output: []
Por quê: edge case: nenhuma requisição

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(n)

Restrições

  • times are in non-decreasing order

Travou na ideia, e não no código? O básico de filas explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado