fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <cassert>
  6. #include <deque>
  7. #include <functional>
  8.  
  9. template <
  10.         class Container,
  11.         class T = typename Container::value_type,
  12.         class size_type = typename Container::size_type>
  13. std::vector<T> sliding_max(const Container & input, size_type m) {
  14.     size_type input_size = input.size();
  15.     if (input_size < m)
  16.         return {};
  17.  
  18.     std::vector<T> result;
  19.     size_t result_size = input_size - m + 1;
  20.     result.reserve(result_size);
  21.  
  22.     struct QueueElem {
  23.         const T & value;
  24.         size_type index;
  25.     };
  26.  
  27.     std::deque<QueueElem> queue;
  28.  
  29.     auto input_it = input.begin();
  30.     for(size_type i = 0; i < m; ++i, ++input_it) {
  31.         QueueElem new_elem{*input_it, i};
  32.         while (!queue.empty() && queue.back().value <= new_elem.value)
  33.             queue.pop_back();
  34.         queue.push_back(new_elem);
  35.     }
  36.     result.push_back(queue.front().value);
  37.  
  38.     for (size_type i = m; i < input_size; ++i, ++input_it) {
  39.         QueueElem new_elem{*input_it, i};
  40.         while (!queue.empty() && queue.back().value <= new_elem.value)
  41.             queue.pop_back();
  42.         queue.push_back(new_elem);
  43.         while (queue.front().index < i - m + 1)
  44.             queue.pop_front();
  45.         result.push_back(queue.front().value);
  46.     }
  47.  
  48.     return result;
  49. }
  50.  
  51.  
  52. int main(){
  53.     std::vector<int> v = {3, 10, 11, 10, 0, 0, 0, 1, 2, 3, 2};
  54.     auto result_max = sliding_max(v, 3);
  55.     assert((result_max == decltype(result_max){11, 11, 11, 10, 0, 1, 2, 3, 3}));
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0s 3412KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/LxWW88
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!