Minimum in sliding window: two different but similar solutions

Правка en4, от oversolver, 2019-11-24 15:25:13

Problem

There are famous problem for given array of numbers and number $$$K$$$ find minimums for all segments of length $$$K$$$.

More general variant: for given array of size $$$n$$$ and $$$q$$$ queries $$$[l_i,r_i]$$$ need to find minimums on segmets at $$$l_i \leq l_{i+1}$$$ и $$$r_i \leq r_{i+1}$$$. Solution must be $$$O(n+q)$$$.

To solve this problem we need sliding window method, we numbers from segments is window. Needed data structure should be able to push_back (add number to the end of window), pop_front (remove first element) и get_min — current minimum in window.

I was surprised to find that there are two types of such data structure. First is very popular and can be easily found in web. But type that I use whole life I can't find. I'll describe both of them.

Решение #1

Идея в том, чтобы хранить последовательность возрастающих минимумов. Первый элемент последовательности равен минимуму всего текущего окна, следом идёт минимум на суффиксе после этого элемента, и так далее. Например, для значений в окне [2,3,1,5,4,8,7,6,9] это будут минимумы [1,4,6,9].

Когда происходит добавление элемента справа (incR, push_back), последовательность меняется следующим образом: все большие элементы убираются, сам элемент добавляется в конец.

Несколько примеров, для [1,4,6,9]:

Добавление 5: [1,4,6,9] -> [1,4] -> [1,4,5]

Добавление 100: [1,4,6,9] -> [1,4,6,9,100]

Добавление 0: [1,4,6,9] -> [] -> [0]

При удалении элемента слева (incL, pop_front) нужно знать, был ли главный минимум первым элементом окна. По значению этого не понять, поэтому в последовательности помимо самих значений нужно хранить в паре с ними позиции этих значении. Пример выше превратится в последовательность [(1,2), (4,4), (6,7), (9,8)], если элементы нумеруются с нуля. Границы текущего окна нужно хранить явно в виде пары чисел $$$L$$$ и $$$R$$$. Итак, если первый элемент последовательности является первым элементом окна, то есть его позиция равна $$$L$$$, то его необходимо просто удалить, более ничего в последовательности не изменится.

Для реализации потребуется структура данных, позволяющая эффективно делать операции удаления слева и справа, а также добавления справа. Для этого можно использовать дек (std::deque в c++)

реализация #1

Решение #2

Представим окно в виде двух стеков: префикс окна находится в левом стеке $$$L$$$ так, что первый элемент окна вверху $$$L$$$, а суффикс окна в правом стеке $$$R$$$ так, что последний элемент окна вверху $$$R$$$.

[2,3,1,5,4,8,7,6,9]
<-------|--------->

L = [5,1,3,2]
R = [4,8,7,6,9]

Когда происходит добавление элемента справа (incR, push_back), элемент попадает в вершину правого стека

При удалении элемента слева (incL, pop_front), элемент уходит с вершины левого стека. Исключение составляет случай, когда в этот момент левый стек пуст. Тогда перед удалением происходит операция перебрасывания правого стека в левый: пока правый стек не закончится, его верхний элемент перемещается в левый стек. Например,

[4,3,1,2]
|------->

L = []
R = [4,3,1,2]

L = [2]
R = [4,3,1]

L = [2,1]
R = [4,3]

L = [2,1,3]
R = [4]

L = [2,1,3,4]
R = []

[4,3,2,1]
<-------|

Теперь, после перебрасывания, из левого стека можно удалять верхний элемент.

Чтобы отвечать в любой момент о текущем минимуме в окне нужно знать минимумы в стеках. Так как правый стек только увеличивается или очищается полностью, его минимум можно поддерживать в отдельной переменной $$$Rmin$$$.

В левом стеке вместо самих значений нужно хранить минимум среди значений от этого элемента до дна стека. Например для стека [5,7,3,4,2,1,8,6] это будет стек [5,5,3,3,2,1,1,1]

Итого, минимум в окне будет равен либо верхнему элементу левого стека, либо $$$Rmin$$$.

реализация #2

Примечание

Оба решения работают за одинаковую ассимптотику. Второе считаю более простым для понимания как алгоритм, но в первом меньше кода. Про сравнительное время работы ничего не могу сказать.

Кстати, оба решения можно проапгрейдить до операции push_front, хотя кажется, такая операция нигде не нужна.

Теги sliding window, rmq, two pointers

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en15 Английский oversolver 2019-11-24 18:36:17 4 Tiny change: '\n\n`[4,3,2,1]` \n`<--' -> '\n\n`[4,3,1,2]` \n`<--'
ru44 Русский oversolver 2019-11-24 18:35:53 4 Мелкая правка: '\n\n`[4,3,2,1]` \n`<--' -> '\n\n`[4,3,1,2]` \n`<--'
ru43 Русский oversolver 2019-11-24 17:25:33 0 (опубликовано)
en14 Английский oversolver 2019-11-24 17:25:24 0 (published)
en13 Английский oversolver 2019-11-24 17:23:14 0 (saved to drafts)
ru42 Русский oversolver 2019-11-24 17:22:58 0 (сохранено в черновиках)
ru41 Русский oversolver 2019-11-24 16:54:03 0 (опубликовано)
en12 Английский oversolver 2019-11-24 16:53:28 0 (published)
ru40 Русский oversolver 2019-11-24 16:52:35 25
en11 Английский oversolver 2019-11-24 16:51:14 29
en10 Английский oversolver 2019-11-24 16:45:56 941
en9 Английский oversolver 2019-11-24 16:01:26 466
en8 Английский oversolver 2019-11-24 15:49:46 671
en7 Английский oversolver 2019-11-24 15:43:22 342
en6 Английский oversolver 2019-11-24 15:38:43 868
en5 Английский oversolver 2019-11-24 15:31:33 762
en4 Английский oversolver 2019-11-24 15:25:13 24
en3 Английский oversolver 2019-11-24 15:23:39 5343
ru39 Русский oversolver 2019-11-24 15:05:07 14 Мелкая правка: 'евый стек.\n\n \n`[4,3,1,' -> 'евый стек. Например,\n\n`[4,3,1,'
ru38 Русский oversolver 2019-11-24 15:03:45 39 Мелкая правка: ' `get_min`~--- текущи' -> ' `get_min`--- текущи'
ru37 Русский oversolver 2019-11-24 15:01:33 419
ru36 Русский oversolver 2019-11-24 14:56:46 36
ru35 Русский oversolver 2019-11-24 14:56:03 386
ru34 Русский oversolver 2019-11-24 14:46:41 4 Мелкая правка: 'зков длины.\n\nБолее' -> 'зков длины $K$.\n\nБолее'
ru33 Русский oversolver 2019-11-24 14:46:07 376
ru32 Русский oversolver 2019-11-24 11:22:46 60
ru31 Русский oversolver 2019-11-24 11:21:05 165
ru30 Русский oversolver 2019-11-24 11:12:19 311
ru29 Русский oversolver 2019-11-24 11:10:10 314
ru28 Русский oversolver 2019-11-24 11:04:23 20 Мелкая правка: '### Решени' -> '### Задача\n\n\n\n\n### Решени'
ru27 Русский oversolver 2019-11-24 11:02:40 148
ru26 Русский oversolver 2019-11-24 11:02:31 378
ru25 Русский oversolver 2019-11-24 10:53:43 712 Мелкая правка: ',7,6,9]` `<------' -> ',7,6,9]` `<------'
ru24 Русский oversolver 2019-11-24 10:47:16 4 Мелкая правка: ',8,7,6,9]`\n`<-------|' -> ',8,7,6,9]` `<-------|'
ru23 Русский oversolver 2019-11-24 10:47:03 128
ru22 Русский oversolver 2019-11-24 10:44:01 11 Возвращено к ru20
ru21 Русский oversolver 2019-11-24 10:43:27 11
ru20 Русский oversolver 2019-11-24 10:40:25 25 Мелкая правка: 'имер, для последовательности `[2,3,1,5' -> 'имер, для значений в окне `[2,3,1,5'
ru19 Русский oversolver 2019-11-24 10:39:48 12
ru18 Русский oversolver 2019-11-24 10:39:12 24
ru17 Русский oversolver 2019-11-24 10:38:12 20
ru16 Русский oversolver 2019-11-24 10:32:22 6
ru15 Русский oversolver 2019-11-24 10:31:56 2 Мелкая правка: 'еров, для [1,4,6,9]:\n\nДобав' -> 'еров, для `[1,4,6,9]`:\n\nДобав'
ru14 Русский oversolver 2019-11-24 07:56:10 18
ru13 Русский oversolver 2019-11-24 07:55:41 15 Мелкая правка: 'Решение #1\n---------\n\nИдея в' -> '### Решение #1\n\nИдея в'
ru12 Русский oversolver 2019-11-24 07:43:27 23
ru11 Русский oversolver 2019-11-24 07:42:18 23
ru10 Русский oversolver 2019-11-24 07:40:50 26 Мелкая правка: 'фывфыв\n\nИдея в' -> 'Решение 1\n---------\n\nИдея в'
ru9 Русский oversolver 2019-11-24 07:39:24 180
ru8 Русский oversolver 2019-11-24 07:36:11 875
ru7 Русский oversolver 2019-11-24 07:23:13 418
ru6 Русский oversolver 2019-11-24 06:45:55 3 Мелкая правка: 'mmary="2">~~~~~\nint' -> 'mmary="2">\n~~~~~\nint'
ru5 Русский oversolver 2019-11-24 06:41:58 9
ru4 Русский oversolver 2019-11-23 21:08:41 1 Мелкая правка: '\n\n<spoiler' -> '\n<spoiler'
en2 Английский oversolver 2019-11-23 21:08:19 5
ru3 Русский oversolver 2019-11-23 20:58:45 560
ru2 Русский oversolver 2019-11-23 20:49:46 676
ru1 Русский oversolver 2019-11-23 20:43:06 64 Первая редакция перевода на Русский (сохранено в черновиках)
en1 Английский oversolver 2019-11-23 20:42:15 69 Initial revision (saved to drafts)