Stack monótono

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 pila creciente/decreciente para hallar, para cada elemento, el siguiente/anterior mayor o menor, en O(n) total.

Complejidad: O(n) (cada índice entra y sale una vez).

Cuándo usarlo

‘Siguiente elemento mayor’, mayor rectángulo en histograma, spans, y como base del convex hull trick.

Implementación recomendada (C++)

// Para cada i, el índice del siguiente elemento mayor a la derecha (o -1).
vector<int> next_greater(const vector<int>& a) {
    int n = a.size(); vector<int> res(n, -1); stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) { res[st.top()] = i; st.pop(); }
        st.push(i);
    }
    return res;
}

⚠️ Notas

Cambia < por <=, el sentido del recorrido o el operador para obtener las 4 variantes (anterior/siguiente, mayor/menor).

🔗 Relacionados