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).