Grade 12 · Data structures and the STLCitește în română

deque: sliding window minimum of length k

Original: deque — minimul pe ferestre de lungime k

O(n)C++1760 lines2 examples

The idea

For every run of k consecutive elements we want the minimum. We keep the 'candidate' positions in a deque, with values increasing from front to back. When a[i] arrives, we pop from the back the positions with value ≥ a[i] (they will never be the minimum again, because a[i] is smaller and stays longer in the window), then push i. From the front we remove the position that has left the window (i - k). The minimum of the window ending at i is always a[front]. Every position enters and leaves only once.

Original description (Romanian)

Pentru fiecare secvență de k elemente consecutive vrem minimul. Ținem într-un deque pozițiile „candidate”, cu valori crescătoare de la față spre spate. Când vine a[i], scoatem din spate pozițiile cu valoare ≥ a[i] (nu vor mai fi niciodată minim, pentru că a[i] e mai mic și rămâne mai mult în fereastră), apoi adăugăm i. Din față scoatem poziția care a ieșit din fereastră (i - k). Minimul ferestrei care se termină în i este mereu a[front]. Fiecare poziție intră și iese o singură dată.

Complexity
O(n)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

8 3
4 2 12 3 8 1 7 5

Expected output

2 2 3 1 1 1
Example 2

Input

4 1
9 8 7 6

Expected output

9 8 7 6

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

deque-minimul-pe-ferestre.cpp
/*
 * Titlu: deque — minimul pe ferestre de lungime k
 * Clasa: 12
 * Capitol: Structuri de date și STL
 * Descriere: Pentru fiecare secvență de k elemente consecutive vrem minimul.
 *            Ținem într-un deque pozițiile „candidate”, cu valori crescătoare de
 *            la față spre spate. Când vine a[i], scoatem din spate pozițiile cu
 *            valoare ≥ a[i] (nu vor mai fi niciodată minim, pentru că a[i] e mai
 *            mic și rămâne mai mult în fereastră), apoi adăugăm i. Din față
 *            scoatem poziția care a ieșit din fereastră (i - k). Minimul ferestrei
 *            care se termină în i este mereu a[front]. Fiecare poziție intră și
 *            iese o singură dată.
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare:
 * 8 3
 * 4 2 12 3 8 1 7 5
 * Ieșire: 2 2 3 1 1 1
 *
 * Exemplu
 * Intrare:
 * 4 1
 * 9 8 7 6
 * Ieșire: 9 8 7 6
 */
#include <deque>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    deque<int> dq;
    bool primul = true;
    for (int i = 0; i < n; i++)
    {
        while (!dq.empty() && a[dq.back()] >= a[i])
            dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k)
            dq.pop_front();
        if (i >= k - 1) // fereastra [i - k + 1, i] este completă
        {
            if (!primul)
                cout << ' ';
            cout << a[dq.front()];
            primul = false;
        }
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.