El 'siguiente elemento mayor' de cada elemento de un array en O(n) usa…
Opciones
- Una pila monótona (Opción correcta)
- Un min-heap
- Búsqueda binaria en una copia ordenada
- Un trie de los valores
Respuesta
Una pila monótona
Por qué
Mantén una pila de índices cuyo siguiente elemento mayor aún no se conoce; sus valores están en orden decreciente (por eso se llama 'monótona').
Cuando un valor nuevo es mayor que la cima de la pila, ES la respuesta para ese elemento: sácalo y registra la respuesta. Repite y luego apila el índice nuevo.
Cada índice entra y sale una vez: O(n).
Recuerda
'Siguiente mayor/menor' → pila monótona.