Минимум в скользящем окне: два похожих, но разных решения

Revision ru31, by oversolver, 2019-11-24 11:21:05

Задача

Решение #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

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

[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
Tags скользящее окно, rmq, два указателя

History

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