Sliding Maximum

In this post I will present a simple and somewhat generic solution for the sliding maximum problem.

Find the maximum element for every K consecutive elements.

Note that the sliding minimum can be seen as a negated sliding maximum problem, just like the maximum spanning tree can be seen as the minimum spanning tree of the negated graph.

Implementation

Below is a generic C++ sliding window I implemented that takes a comparator as a template parameter. This allows it to be instantiated for both the sliding maximum and the sliding minimum.

template <typename T, typename Comparator>
class SlidingWindow {
  struct Block {
    Block(T v, size_t w) : value(v), width(w) {}
    T value;
    size_t width;
  };
  Comparator comp;
  deque<Block> data;

 public:
  void push(const T t) {
    size_t width = 1;
    while (!data.empty() && comp(data.back().value, t)) {
      data.pop_back();
      width++;
    }
    data.emplace_back(t, width);
  }
  T get() const { return data.front().value; }
  void pop() {
    // Either reduce the width of the best block (front), or drop it.
    if (data.empty()) {
      return;
    }
    if (data.front().width > 1) {
      data.front().width--;
    } else {
      data.pop_front();
    }
  }
};

This solution is amortized \(O(1)\) for all operations, making it \(O(N)\) for \(N\) elements. By using the standard library trees directly we cannot do better than \(O(N \log N)\).

Sliding Maximum Example

Using 20 terms and a window of width 4, we have the following table: