Pila monótona: siguiente elemento mayor
Responda consultas de amplitud en una sola pasada
Pila monótona: siguiente elemento mayor es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El problema del siguiente mayor
Para cada número, quiere encontrar el primer valor mayor a su derecha. La fuerza bruta cuesta O(n al cuadrado), pero una pila monótona lo resuelve en un solo recorrido.
Qué significa monótona
Una pila monótona mantiene sus valores ordenados, en este caso de forma decreciente, así que sabemos que se ha encontrado una respuesta justo cuando ese orden se rompería.
Guardar índices, no valores
Apile índices en lugar de números sin más. Así sabrá exactamente qué posición debe rellenar cuando aparezca un elemento mayor.
stack = []
ans = [-1] * len(nums)Recorrer de izquierda a derecha
Recorra el arreglo una sola vez. En cada índice, extraerá elementos ya resueltos o apilará el índice actual para más adelante.
for i in range(len(nums)):Desapilar los menores
Mientras el valor actual sea mayor que el valor del índice situado en la cima, ese índice por fin habrá encontrado su siguiente elemento mayor.
while stack and nums[i] > nums[stack[-1]]:Registrar la respuesta
Extraiga el índice de la cima y establezca su respuesta como el valor actual. Cada índice se resuelve exactamente una vez, lo que mantiene el trabajo lineal.
j = stack.pop()
ans[j] = nums[i]Apilar y continuar
Después de resolver todos los elementos menores, apile el índice actual para que espere a su propio elemento mayor futuro.
stack.append(i)Los elementos restantes no tienen respuesta
Los índices que siguen en la pila al final nunca encontraron un valor mayor. Conservan su valor predeterminado de -1, que significa que no existe ninguno.
Por qué es O(n)
Cada índice se apila una vez y se desapila una vez. Aunque haya un bucle while interno, el trabajo total sigue siendo lineal en todo el recorrido.
Cambiar para buscar el siguiente menor
¿Necesita el siguiente elemento menor? Mantenga la pila en orden creciente invirtiendo la comparación de mayor que a menor que.
while stack and nums[i] < nums[stack[-1]]:Un patrón, no un truco
Las consultas de intervalos, los precios de acciones y las áreas de histogramas reutilizan esta idea. La pila monótona es un patrón fundamental de concursos que merece la pena memorizar.
Comprobación rápida
Resuelve el problema del siguiente elemento mayor con una pila monótona. ¿Por qué el tiempo total es lineal?
Resumen: un recorrido, muchas respuestas
Ha utilizado una pila monótona decreciente de índices para encontrar los siguientes elementos mayores en O(n). Este patrón permite resolver muchos problemas de intervalos. 🚀
Preguntas frecuentes
¿La lección «Pila monótona: siguiente elemento mayor» es gratis?
Sí — el texto completo de «Pila monótona: siguiente elemento mayor» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Pila monótona: siguiente elemento mayor»?
Responda consultas de amplitud en una sola pasada Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Pila monótona: siguiente elemento mayor»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Pilas para emparejar corchetes
- Pila monótona: siguiente elemento mayor
- Colas y collections.deque
- Máximo de ventana deslizante con deque