Búsqueda del siguiente valor mayor
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
Recorrer hacia la derecha desde la posición de cada consulta funciona, pero es cuadrático cuando muchos valores esperan mucho tiempo a uno mayor. ¿Puede una sola pasada sobre nums responder por todos los valores a la vez?
Guarda los valores que todavía esperan uno mayor. Cuando llega un valor nuevo, cada valor en espera más pequeño que él acaba de encontrar su respuesta. Los valores en espera siempre forman una secuencia descendente, así que los más pequeños quedan arriba.
Recorre nums con una pila. Mientras el tope de la pila sea menor que el valor actual, haz pop y registra el valor actual como su respuesta en un diccionario. Haz push del valor actual. Al final, busca cada consulta en el diccionario, con -1 por defecto.
- Tiempo objetivo
- O(n + q)
- Espacio objetivo
- O(n + q)
Restricciones
- nums holds distinct integers
- every query value appears in nums
Solución
Un valor espera en la pila (stack) hasta que llega el primer valor mayor, y en ese momento está en el tope, porque todo lo que se apiló después y sigue esperando es menor que él. Así que una sola pasada de izquierda a derecha hace pop de cada valor justo cuando aparece su respuesta y registra el par en un diccionario, y lo que siga en la pila al final nunca obtuvo respuesta. Después, las consultas son simples búsquedas. Cada valor entra y sale de la pila como máximo una vez, así que el tiempo es O(n + q) y el espacio es O(n).
def next_greater_lookup(nums, queries):
answer = {}
stack = [] # waiting values, falling from bottom to top
for x in nums:
while stack and stack[-1] < x:
answer[stack.pop()] = x # x is the first larger value after it
stack.append(x)
return [answer.get(q, -1) for q in queries]
print(next_greater_lookup([4, 1, 3, 6, 2, 5], [1, 3, 2, 6])) # -> [3, 6, 5, -1]
print(next_greater_lookup([5, 4, 3, 2, 1], [4, 1])) # -> [-1, -1]
print(next_greater_lookup([7], [7])) # -> [-1]¿Lo que te frena es la idea y no el código? Pila monótona lo explica.