Concepto Fundamental

Una cola monótona es una estructura de datos especializada donde sus elementos permanecen siempre ordenados, ya sea de forma estrictamente ascendente o descendente. Esta propiedad se preserva realizando modificaciones estratégicas tanto al inicio (encabezado) como al final (cola) de la estructura durante las inserciones y eliminaciones.

Aplicación en Ventanas Deslizantes

La utilidad principal de esta técnica reside en la resolución eficiente de problemas que requieren encontrar el máximo o el mínimo dentro de un rango subsecuente de tamaño fijo mientras este se desplaza sobre un conjunto de datos. A continuación, se presenta un caso clásico donde debemos calcular los valores extremos para cada posición de ventana.

Ejemplo de Evolución de Datos

Dada una secuencia numérica y un tamaño de ventana especificado, el sistema debe identificar el menor y mayor valor existente en ese intervalo móvil.

Especificaciones de Entrada y Salida

El programa recibe inicialmente dos enteros positivos: el número total de elementos (N) y el tamaño de la ventana (K). Posteriormente, se proporciona la secuencia completa de datos.

• Entrada: Dos líneas. La primera contiene N y K. La segunda lista N enteros.
• Salida: Dos líneas. La primera muestra los mínimos de cada ventana; la segunda, los máximos.

Para grandes volúmenes de datos (donde N puede llegar hasta $10^6$), una solución ingenua de fuerza bruta ($O(N^2)$) resultará inviable. Por ello, es imperativo aplicar la estrategia de colas monótonas para alcanzar una complejidad lineal $O(N)$.

Detalle del Algoritmo

El núcleo de la solución consiste en mantener dos estructuras auxiliares: una para maximizar y otra para minimizar.

1. Mantenimiento de Orden: Antes de insertar un nuevo elemento, se comparan estos con los últimos elementos almacenados. Si buscaoms el máximo, eliminamos de la cola aquellos valores menores que el actual, garantizando así una cola decreciente. Para el mínimo, sucede lo contrario, eliminando valores mayores para asegurar un orden creciente.
2. Validad de Rango: Cada vez que avanza la ventana, debemos verificar si el índice en la cabeza de la cola ha quedado fuera del rango actual de tamaño K. Si el desplazamiento excede el límite, el elemento anterior se descarta inmediatamente.

Código de Referencia

A continuación se muestra una implementación típica en C++. Se han renombrado las variables y reorganizado la lógica interna para separar claramente el proceso de mantenimiento de las colas de incremento y decremento.

using namespace std;

// Definición de tipos para claridad using LongInt = long long; const int MAX_SIZE = 1000005;

int n, k; LongInt sequence[MAX_SIZE];

int main() { // Optimización de entrada/salida ios_base::sync_with_stdio(false); cin.tie(nullptr);

if (!(cin >> n >> k)) return 0;

// Lectura de la secuencia base
for (int i = 0; i < n; ++i) {
    cin >> sequence[i];
}

// Arrays simulando las colas para máximos (monótonos descendentes)
// val_max: almacena los valores reales
// idx_max: almacena las posiciones originales (índices)
LongInt val_max[MAX_SIZE];
int idx_max[MAX_SIZE];
int head_max = 0, tail_max = 0;

// Iteración para hallar Máximos en la ventana
for (int i = 0; i < n; ++i) {
    // Eliminar elementos fuera del rango actual desde el frente
    if (head_max <= tail_max && i - idx_max[head_max] >= k) {
        head_max++;
    }

    // Mantener orden descendente: borrar valores menores que el nuevo desde atrás
    while (head_max <= tail_max && val_max[tail_max] < sequence[i]) {
        tail_max--;
    }

    // Insertar nuevo valor en la cola
    tail_max++;
    val_max[tail_max] = sequence[i];
    idx_max[tail_max] = i;

    // Imprimir resultado si la ventana está completa
    if (i + 1 >= k) {
        cout << val_max[head_max] << " ";
    }
}
cout << "\n";

// Re-inicializar punteros para Mínimos
int head_min = 0, tail_min = 0;
LongInt val_min[MAX_SIZE];
int idx_min[MAX_SIZE];

// Iteración para hallar Mínimos en la ventana (Lógica idéntica pero orden inverso)
for (int i = 0; i < n; ++i) {
    // Validar expiración de elementos en el encabezado
    if (head_min <= tail_min && i - idx_min[head_min] >= k) {
        head_min++;
    }

    // Mantener orden ascendente: borrar valores mayores que el nuevo desde atrás
    while (head_min <= tail_min && val_min[tail_min] > sequence[i]) {
        tail_min--;
    }

    // Añadir nuevo elemento
    tail_min++;
    val_min[tail_min] = sequence[i];
    idx_min[tail_min] = i;

    // Output correspondiente
    if (i + 1 >= k) {
        cout << val_min[head_min] << " ";
    }
}

return 0;

}

</div>