Minimum in sliding window: two different but similar solutions

Правка en5, от oversolver, 2019-11-24 15:31:33

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.

Solution #1

The idea is to store sequence of increasing minimums. First minimum is minimum of whole window, second is minimum of elements after first minimum, and so on. For example, for window [2,3,1,5,4,8,7,6,9] sequence is [1,4,6,9].

When element is adding to the right of window (incR, push_back), the sequence changes as follows: all higher elements are gone from sequence, new element is goes to the end of sequence.

Couple of samples for [1,4,6,9]:

Adding 5: [1,4,6,9] -> [1,4] -> [1,4,5]

Adding 100: [1,4,6,9] -> [1,4,6,9,100]

Adding 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)