Минимум в скользящем окне с быстрыми add и getMin
Реализуйте скользящее окно целых чисел фиксированного размера: add(value) добавляет значение и, когда окно превышает размер w, удаляет самое старое; getMin() возвращает текущий минимум окна.
Ограничения:
- обе операции должны быть сублинейными —
O(log w)на вызов или лучше, неO(w) - окно хранит порядок вставки, чтобы вытеснялся нужный элемент
class SlidingWindowMin {
SlidingWindowMin(int w) { /* ваш код здесь */ }
void add(int value) { /* ваш код здесь */ }
int getMin() { /* ваш код здесь */ }
}Допишите реализацию.
Держите TreeMap<value,count> плюс FIFO-очередь со значениями окна в порядке вставки. В add, если окно полно, извлеките самое старое из очереди и уменьшите (или удалите) его счётчик в map; затем увеличьте счётчик нового значения и поставьте его в очередь. getMin возвращает map.firstKey(). Каждая операция O(log w); монотонный deque даёт амортизированную O(1).
- ✗Пересканировать всё окно для минимума на каждый
getMin, что даётO(w) - ✗Использовать heap и считать, что его голова — это и самый старый элемент для удаления
- ✗Хранить только один текущий минимум, что ломается, когда он вытесняется
- →Почему
TreeMapиз значения в счётчик корректно обрабатывает дубликаты значений? - →Как монотонный deque достигает амортизированной
O(1)для этой задачи?
Решение
class SlidingWindowMin {
private final int w;
private final NavigableMap<Integer, Integer> counts = new TreeMap<>();
private final Deque<Integer> order = new ArrayDeque<>();
SlidingWindowMin(int w) { this.w = w; }
void add(int value) {
if (order.size() == w) { // окно полно — выбросить старейший
int old = order.poll();
counts.merge(old, -1, Integer::sum);
if (counts.get(old) == 0) counts.remove(old);
}
counts.merge(value, 1, Integer::sum); // учесть новое значение
order.add(value);
}
int getMin() { return counts.firstKey(); } // наименьший ключ TreeMap
}Идея. TreeMap хранит значения в отсортированном виде, поэтому firstKey() даёт минимум за O(log w). Счётчик count нужен, чтобы корректно работать с дубликатами: вытеснение одного вхождения уменьшает счётчик, а ключ удаляется только когда счётчик дошёл до нуля. FIFO-очередь order фиксирует порядок вставки, чтобы удалять именно самый старый элемент.
Каждая операция — O(log w). Оптимум — монотонный deque индексов: он даёт амортизированную O(1), удерживая по убыванию кандидатов на минимум, но его сложнее реализовать корректно с учётом окна.
