Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан класс RecentCounter, который подсчитывает количество последних вызовов за определенный период времени. Реализуйте этот класс.
Конструктор RecentCounter инициализирует счетчик с нулевым количеством последних вызовов.
Класс имеет метод ping, который принимает в качестве аргумента параметр t (время в миллисекундах последнего вызова) и в качестве ответа возвращает количество вызовов, произошедших за последние 3000 мс.
Гарантируется, что каждый вызов ping использует строго большее значение t, чем предыдущий вызов.
⚠️ Ограничения
— Значение t находится в диапазоне от 1 до 10^9
— Каждый пример будет вызывать ping со строго возрастающими значениями t
— Для проверки будет совершено не более 10^4 вызовов метода ping
1️⃣ Пример
```golang
counter := Constructor()
counter.Ping(1)
counter.Ping(100)
counter.Ping(3001)
counter.Ping(3002)
counter.Ping(3003)
```
Ответ: 4
Пояснение: За последние 3000 мс было сделано 4 вызова в следующее время [100, 3001, 3002, 3003].
2️⃣ Пример
counter := Constructor()
counter.Ping(1)
counter.Ping(100)
counter.Ping(3001)
Ответ: 3
Пояснение: За последние 3000 мс было сделано 4 вызова в следующее время [1, 100, 3001].
✅ Решение
Эта задача решается буквально в несколько строчек.
Для хранения вызовов определим массив calls внутри класса, который при инициализации экземпляра получает значение пустого массива.
Далее в реализации метода ping сначала надо добавить время нового вызова в массив calls, а потом удалить из начала все элементы, которые вываливаются из интервала в 3000 миллисекунд, тем самым реализовав простую очередь. В конце нужно лишь вернуть длину оставшегося массива.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
Основная временная сложность нашего метода ping заключается в цикле, который в худшем случае будет выполнять 3000 итераций для извлечения всех устаревших элементов, а в лучшем случае — одну итерацию. Исходя из этого сложность равна O(3000) = O(1).
По памяти
Сложность O(1), так как максимальная длина нашего массива вызовов — 3000 элементов. По условию задачи, каждое новое значение в нем является целым числом и строго больше предыдущего, поэтому мы точно можем определить максимальный размер массива.
#queue #easy