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

Revision ru7, by oversolver, 2019-11-24 07:23:13

фывфыв

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

Когда происходит расширение окна вправо, новый элемент убрать всё большие элементы из этой последовательности

решение 1
решение 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)