Problemas con Pilas y Colas

Problema 1: Siguiente elemento mayor (Next Greater Element)

Problema: Para cada elemento de un arreglo, encuentra el siguiente elemento que sea mayor.

Entrada: [4, 5, 2, 10, 8]
Salida:  [5, 10, 10, -1, -1]

Para el 4, el siguiente mayor es 5. Para el 5, es 10. Para el 10, no hay → -1.

Solución con pila monótona

vector<int> siguienteMayor(vector<int> &v) {
    int n = v.size();
    vector<int> resultado(n, -1);
    stack<int> pila;  // Guarda índices

    for (int i = 0; i < n; i++) {
        while (!pila.empty() && v[pila.top()] < v[i]) {
            resultado[pila.top()] = v[i];
            pila.pop();
        }
        pila.push(i);
    }

    return resultado;
}

Complejidad: $O(n)$ — cada elemento entra y sale de la pila exactamente una vez.

Problema 2: Máximo en ventana deslizante

Problema: Dado un arreglo y una ventana de tamaño K, encuentra el máximo en cada posición de la ventana.

Arreglo: [1, 3, -1, -3, 5, 3, 6, 7], K=3
Ventanas: [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]
Máximos:   3,        3,         5,         5,        6,       7

Solución con deque

vector<int> maxVentana(vector<int> &v, int k) {
    deque<int> dq;  // Guarda índices
    vector<int> resultado;

    for (int i = 0; i < v.size(); i++) {
        // Quitar elementos fuera de la ventana
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // Quitar elementos menores que el actual
        while (!dq.empty() && v[dq.back()] <= v[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        if (i >= k - 1) {
            resultado.push_back(v[dq.front()]);
        }
    }

    return resultado;
}

Problema 3: Área máxima del histograma

Problema: Dado un histograma (barras de diferentes alturas), encuentra el rectángulo de área máxima.

Alturas: [2, 1, 5, 6, 2, 3]

     ██
    ████
    ████
    ████ ██
 ██ ██████
 █████████

El rectángulo más grande tiene área 10 (alturas 5 y 6, ancho 2).

Solución con pila

int maxAreaHistograma(vector<int> &alturas) {
    stack<int> pila;
    int maxArea = 0;
    int n = alturas.size();

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : alturas[i];

        while (!pila.empty() && alturas[pila.top()] > h) {
            int altura = alturas[pila.top()];
            pila.pop();
            int ancho = pila.empty() ? i : (i - pila.top() - 1);
            maxArea = max(maxArea, altura * ancho);
        }

        pila.push(i);
    }

    return maxArea;
}

Problema 4: Simulación con cola - Josephus simplificado

Problema: N personas en círculo. Cada K personas, una sale. ¿Quién queda al final?

int josephus(int n, int k) {
    queue<int> cola;
    for (int i = 1; i <= n; i++) cola.push(i);

    while (cola.size() > 1) {
        for (int i = 0; i < k - 1; i++) {
            cola.push(cola.front());  // Mover al final
            cola.pop();
        }
        cola.pop();  // Eliminar el k-ésimo
    }

    return cola.front();
}

Problema 5: Cola de prioridad - K elementos más grandes

Problema: Dado un arreglo, encuentra los K elementos más grandes.

vector<int> kMasGrandes(vector<int> &v, int k) {
    // Min-heap de tamaño k
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int x : v) {
        pq.push(x);
        if (pq.size() > k) pq.pop();
    }

    vector<int> resultado;
    while (!pq.empty()) {
        resultado.push_back(pq.top());
        pq.pop();
    }
    return resultado;
}

Complejidad: $O(n \log k)$, mejor que ordenar todo el arreglo cuando $k \ll n$.

Resumen de cuándo usar cada estructura

Ejercicio de práctica

Dado un string con paréntesis ( y ), encuentra la longitud del substring de paréntesis válidos más largo.

Entrada: (() → Salida: 2 Entrada: )()()) → Salida: 4

#include <iostream>
#include <stack>
using namespace std;

int main() {
    string s;
    cin >> s;

    stack<int> pila;
    pila.push(-1);  // Marca del inicio
    int maxLen = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            pila.push(i);
        } else {
            pila.pop();
            if (pila.empty()) {
                pila.push(i);
            } else {
                maxLen = max(maxLen, i - pila.top());
            }
        }
    }

    cout << maxLen << endl;

    return 0;
}

Siguiente paso

Aprende sobre Búsqueda Binaria, una de las técnicas más poderosas en competencias.