Saltar al contenido

Búsqueda del siguiente valor mayor

Fácil#monotonic-stack#hash-map~15 min

La misión

Problema

Recibes una lista nums de enteros distintos y una lista queries cuyos valores aparecen todos en algún lugar de nums. Para cada valor de consulta (query), encuentra el primer valor a su derecha en nums que sea mayor que él, o -1 cuando no le sigue ningún valor mayor. Devuelve las respuestas en el orden de las consultas.

Ejemplos

Input:  nums = [4, 1, 3, 6, 2, 5], queries = [1, 3, 2, 6]
Output: [3, 6, 5, -1]
Por qué: a 1 le sigue 3, a 3 le sigue 6 y a 2 le sigue 5, mientras que después de 6 no hay nada mayor
Input:  nums = [5, 4, 3, 2, 1], queries = [4, 1]
Output: [-1, -1]
Por qué: la lista solo baja, así que ningún valor tiene uno mayor después
Input:  nums = [7], queries = [7]
Output: [-1]
Por qué: caso límite: un solo valor no tiene nada a su derecha

Pistas

0 / 3

Tiempo objetivo
O(n + q)
Espacio objetivo
O(n + q)

Restricciones

  • nums holds distinct integers
  • every query value appears in nums

¿Lo que te frena es la idea y no el código? Pila monótona lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio