Deque monótona (ventana deslizante)

Tema: Estructuras de Datos · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Mantiene una cola doble con los candidatos de una ventana en orden decreciente (o creciente), de modo que el frente es siempre el máximo (o el mínimo) de la ventana actual. Responde el máximo de cada ventana de largo k en O(n) total, sin estructuras pesadas.

Complejidad: O(n) amortizado: cada índice entra y sale de la deque exactamente una vez. La versión 2D sobre una matriz n×m es O(n·m).

Cuándo usarlo

Máximo/mínimo de cada ventana de largo fijo, y como acelerador de DPs cuya transición es dp[i] = min(dp[j]) + algo sobre una ventana de j. En 2D, máximo de cada submatriz k×k.

Implementación recomendada (C++)

// Máximo de cada ventana de largo k, en O(n). La deque guarda ÍNDICES cuyos
// valores van en orden DECRECIENTE: por eso el frente es siempre el máximo.
vector<int> max_ventana(const vector<int>& a, int k) {
    deque<int> dq;                        // índices, no valores
    vector<int> res;
    for (int i = 0; i < (int)a.size(); i++) {
        if (!dq.empty() && dq.front() <= i - k) dq.pop_front();    // se salió por la izquierda
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // ya no puede ganarle a a[i]
        dq.push_back(i);
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}
 
// Máximo de cada submatriz k×k: una pasada por filas y otra por columnas.
vector<vector<int>> max_submatriz(const vector<vector<int>>& g, int k) {
    int n = g.size(), m = g[0].size();
    vector<vector<int>> filas(n);
    for (int i = 0; i < n; i++) filas[i] = max_ventana(g[i], k);   // n × (m-k+1)
    vector<vector<int>> res(n - k + 1, vector<int>(m - k + 1));
    for (int j = 0; j < (int)filas[0].size(); j++) {
        vector<int> col(n);
        for (int i = 0; i < n; i++) col[i] = filas[i][j];
        vector<int> v = max_ventana(col, k);                       // (n-k+1) por columna
        for (int i = 0; i < (int)v.size(); i++) res[i][j] = v[i];
    }
    return res;
}

⚠️ Notas

Por qué queda monótona, y por qué eso da O(n): antes de meter i sacas por atrás a todo el que valga menos o igual que a[i]. Y con razón: cualquier ventana futura que contenga a uno de esos también contiene a i (porque i es más nuevo y las ventanas son contiguas), así que ese candidato ya no puede ser máximo nunca más. Lo que queda es una secuencia decreciente, y como cada índice entra una vez y sale una vez, el total es O(n) aunque el while de adentro parezca caro — el mismo argumento amortizado del Stack monótono, que es su hermana: la pila resuelve el siguiente mayor, la deque resuelve el máximo de una ventana.

⚠️ Guarda índices, no valores. Es lo único que te permite saber cuándo un candidato se salió por la izquierda. Y el pop_front es un if, no un while: en cada paso expira a lo más un índice.

Sobre <= vs < al sacar por atrás: las dos versiones devuelven el máximo correcto (está probado con arreglos enteros de valores repetidos). Con <= la deque queda más chica y el frente es el índice más nuevo entre los máximos; con < es el más antiguo. Solo importa si lo que necesitas es el índice y no el valor. Para el mínimo, invierte esa comparación a >=.

La versión 2D es la que pide Roberto el constructor (OCI 2020 Nacional), que aparece como desafío del módulo 19: primero colapsas cada fila a los máximos de sus ventanas horizontales, y después aplicas lo mismo por columnas sobre ese resultado. Si la ventana no es de largo fijo sino que crece y se encoge según una condición, lo que quieres es Dos punteros y ventana deslizante; si además necesitas consultas arbitrarias sobre datos que cambian, ahí sí toca un Segment tree.

🔗 Relacionados