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

Правка ru2, от oversolver, 2019-11-23 20:49:46

1

2

int inf = 2e9;
struct sliding_window{
    vector<int> l, r;
    int rmin;
    
    sliding_window(){
        rmin = inf;
    }
    
    void push_back(int x){
        r.push_back(x);
        rmin = min(rmin, x);
    }
    
    void pop_front(){
        if(l.empty()){
            for(int mn = inf; !r.empty();){
                mn = min(mn, r.back());
                l.push_back(mn);
                r.pop_back();
            }
            rmin = inf;
        }
        l.pop_back();
    }
    
    int get_min(){
        int res = rmin;
        if(!l.empty()) res = min(res, l.back());
        return res;
    }
};
Теги скользящее окно, rmq, два указателя

История

 
 
 
 
Правки
 
 
  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)