Вычисление движущегося максимума

Question

Возможный дубликат:
Найти минимальное число во всех смежных подмассивах размера l массива размера n

У меня есть (большой) массив числовых данных (размер N) и хотел бы вычислить массив работающих максимумов с фиксированным размером окна w,

Более прямо, я могу определить новый массив out[k-w+1] = max{data[k-w+1,...,k]} за k >= w-1 (это предполагает массивы на основе 0, как в C++).

Есть ли лучший способ сделать это, чем N log(w)?

[Я надеюсь, что должен быть линейный в N вне зависимости от w, как для скользящего среднего, но не могу найти его. За N log(w) Я думаю, что есть способ управлять с отсортированной структурой данных, которая будет делать insert(), delete() а также extract_max() в целом log(w) или меньше на структуре размера w - например, сортированное двоичное дерево].

Большое спасибо.

Answer 1

Действительно, существует алгоритм, который может сделать это за O(N) время без зависимости от размера окна w. Идея состоит в том, чтобы использовать умную структуру данных, которая поддерживает следующие операции:

• Enqueue, который добавляет новый элемент в структуру,
• Dequeue, который удаляет самый старый элемент из структуры, и
• Find-max, который возвращает (но не удаляет) минимальный элемент из структуры.

По сути, это структура данных очереди, которая поддерживает доступ (но не удаление) максимального элемента. Удивительно, но, как видно из этого более раннего вопроса, можно реализовать эту структуру данных таким образом, чтобы каждая из этих операций выполнялась за амортизированное время O(1). В результате, если вы используете эту структуру для постановки в очередь w элементов, а затем непрерывного удаления из очереди и помещения в очередь другого элемента в структуре при вызове find-max по мере необходимости, потребуется только O(n + Q) время, где Q - число запросы вы делаете. Если вы заботитесь о минимуме каждого окна только один раз, это в конечном итоге будет O(n), независимо от размера окна.

Надеюсь это поможет!

Answer 2

Я продемонстрирую, как это сделать с помощью списка:

L = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6]

с длиной N=23 а также W = 4,

Сделайте две новые копии вашего списка:

L1 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6]
L2 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6]

Петля от i=0 в N-1, Если i не делится на Wзатем заменить L1[i] с max(L1[i],L1[i-1]),

L1 = [21, 21, 21, 21, | 3, 9, 11, 18, | 19, 19, 19, 23 | 20, 20, 20, 20 | 1, 2, 22, 22 | 8, 12, 12]

Петля от i=N-2 в0, Если i+1 не делится на Wзатем заменить L2[i] с max(L2[i], L2[i+1]),

L2 = [21, 17, 16, 7 | 18, 18, 18, 18 | 23, 23, 23, 23 | 20, 15, 14, 14 | 22, 22, 22, 13 | 12, 12, 6]

Сделай список L3 длины N + 1 - W, чтобы L3[i] = max(L2[i], L1[i + W - 1])

L3 = [21, 17, 16, 11 | 18, 19, 19, 19 | 23, 23, 23, 23 | 20, 15, 14, 22 | 22, 22, 22, 13]

Тогда этот список L3 движущиеся максимумы вы ищете, L2[i] это максимум диапазона между i и следующая вертикальная линия, в то время как l1[i + W - 1] это максимум диапазона между вертикальной линией и i + W - 1,