Next Greater Element I
Recibes dos arreglos de enteros distintos, nums1 y nums2, y todos los valores de nums1 también aparecen en nums2. El siguiente elemento mayor de un valor x es el primer valor a la derecha de x en nums2 que sea mayor que x, o -1 si no existe tal valor.
Devuelve un arreglo que contenga el siguiente elemento mayor de cada valor de nums1, en el orden de nums1.
Función
- nums1integer-array
- los valores que se deben responder, todos ellos encontrados en nums2
- nums2integer-array
- el arreglo en el que buscas a la derecha de cada valor
- Devuelveinteger-array
- el siguiente elemento mayor de cada valor de nums1, o -1, en el orden de nums1
Restricciones
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104- Todos los valores de
nums1son distintos, y todos los valores denums2son distintos. - Cada valor de
nums1aparece ennums2.
Ejemplos
- Entrada
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- Salida
- [8, -1, 6]
- Explicación
- Después del 3 en
nums2vienen 8 y 2, y 8 es el primero que es mayor que 3. Después del 8 solo viene 2, así que a 8 le corresponde -1. El valor justo después de 1 es 6, que ya es mayor.
- Entrada
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- Salida
- [-1, 9]
- Explicación
- Solo 4 sigue al 5, y 4 es menor, así que 5 obtiene -1. El valor justo después de 2 es 9. Las respuestas siguen el orden de
nums1, no el orden denums2.
- Entrada
- nums1 = [10, 0]nums2 = [0, 10, 11]
- Salida
- [11, 10]
- Explicación
- El primer valor después de 10 es 11. El primer valor después de 0 es 10, que es mayor, así que 0 obtiene 10 aunque 11 viene después y es aún mayor.
+14 pruebas ocultas al enviar
Para ir más allá
Para cada posición de nums2, ¿puedes devolver cuántos pasos a la derecha está su siguiente elemento mayor, en una sola pasada?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Recorrer hacia la derecha desde cada valor de
nums1puede costar hasta 10^4 pasos por valor. Las respuestas dependen solo denums2. ¿Podrías calcular el siguiente elemento mayor de cada valor denums2en una sola pasada y después buscar los valores denums1?Recorre
nums2de izquierda a derecha y conserva los valores que aún no han encontrado un valor mayor. Cuando llega un valor nuevo, es la respuesta para todos los valores menores que están esperando. Los valores en espera siempre forman una secuencia decreciente, así que los menores quedan en la parte superior de una pila.Para cada valor de
nums2: mientras el valor en la cima de la pila sea menor que este, saca el valor de la cima y registra el valor actual como su respuesta en un mapa hash. Después, apila el valor actual. Al final, responde con el valor correspondiente del mapa para cada valor denums1, usando -1 para un valor que nunca se sacó de la pila.
Solución
Para un valor, la respuesta se obtiene recorriendo hacia la derecha, pero recorrer todos los valores de nums1 cuesta hasta nums1.length × nums2.length pasos. Las respuestas dependen únicamente de nums2, así que puedes encontrar de una vez el siguiente elemento mayor de cada valor de nums2 con una pila monótona, guardarlos en un mapa hash y responder las consultas de nums1 mediante búsquedas.
Encuentra cada valor y recorre hacia la derecha
Correcto, pero no termina con las pruebas más grandes
Intuición
Haz lo que dice la definición. Para un valor x de nums1, recorre nums2 hasta llegar a x. Después sigue recorriendo y detente en el primer valor mayor que x. Si llegas al final sin encontrar ninguno, la respuesta es -1.
Esto es correcto porque el recorrido visita los valores a la derecha de x en orden, así que el primer valor mayor que encuentra es el primer valor mayor que hay.
Es lento cuando las respuestas están muy lejos o no existen. Si nums2 está en orden decreciente, ningún recorrido encuentra un valor mayor y cada valor de nums1 se recorre hasta el final. Con m valores en nums1 y n en nums2, eso supone hasta m × n pasos: 10^8 cuando ambos arreglos contienen 10^4 valores. Además, cada recorrido vuelve a cubrir terreno que los anteriores ya recorrieron.
Algoritmo
- Recorre cada valor
xdenums1. - Encuentra el índice
jdondenums2[j]es igual ax. - Recorre
nums2desdej+1y detente en el primer valor mayor quex. - Añade ese valor o -1 si el recorrido llegó al final.
- Devuelve las respuestas recopiladas.
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return resultPila monótona y mapa hash
Intuición
Dale la vuelta al problema. En lugar de preguntar, para cada valor, qué viene después, recorre nums2 una vez y deja que cada nuevo valor responda por los valores anteriores a los que supera. Mantén en una pila los valores que aún no tienen respuesta. Cuando llega un valor, saca de la parte superior todos los valores menores: el nuevo valor es el primer valor mayor a su derecha, así que esa es su respuesta. Luego inserta el nuevo valor, que todavía está esperando su propia respuesta.
Recorre nums2 = [1, 6, 3, 8, 2]. Inserta 1. Después llega 6 y supera a 1, así que 1 se asocia con 6; inserta 6. Después llega 3, no supera a 6 y se inserta encima: la pila es [6, 3]. Después, 8 saca 3 y 6, así que ambos se asocian con 8; inserta 8. Después se inserta 2. La pila termina como [8, 2], y esos dos valores no tienen respuesta. Para nums1 = [3, 8, 1], el mapa da [8, -1, 6].
La pila siempre está en orden decreciente de abajo arriba, porque un valor se inserta solo después de sacar todos los valores menores que están encima. Por eso solo necesitas mirar la parte superior. Un valor sale de la pila en cuanto aparece el primer valor mayor, así que la respuesta que registras es el primero, no el mayor.
Cada valor de nums2 se inserta una vez y se saca como máximo una vez, así que el bucle interno realiza como máximo n extracciones en total durante todo el recorrido. Con las m búsquedas, el tiempo es O(n + m). El mapa es lo que conecta los dos arreglos: los valores son distintos, así que un valor es una clave segura, aunque esté en posiciones diferentes en nums1 y nums2. Las soluciones en C y R usan como mapa un arreglo de 10^4+1 posiciones indexado por valor, lo cual funciona porque ningún valor supera 10^4.
Algoritmo
- Crea un mapa vacío y una pila vacía.
- Para cada valor de
nums2, desapila todos los valores menores que estén en la parte superior de la pila y asígnalos en el mapa al valor actual. - Apila el valor actual.
- Para cada valor de
nums1, devuelve la respuesta asignada en el mapa, o -1 si no tiene ninguna.
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
Errores comunes y casos límite
La pila en sí es código corto; los errores están en lo que registras y dónde buscas.
- Registrar el valor más grande a la derecha en lugar del primero que sea mayor. En
nums2 = [3, 5, 1, 2, 4, 9, 0], la respuesta para 1 es 2, no 9. - Devolver las respuestas en el orden de
nums2, o para cada valor denums2. El resultado tiene una entrada por cada valor denums1, en su orden. - Devolver un índice en lugar de un valor. El problema pide el valor mayor en sí.
- Leer
nums2en el índice que tiene un valor ennums1. El mismo valor ocupa posiciones distintas en los dos arreglos; búscalo por valor, que es para lo que sirve el mapa. - Olvidar los valores que quedan en la pila al final. Nunca encontraron un valor mayor, así que su respuesta es -1; una búsqueda en el mapa sin valor predeterminado falla o no devuelve nada para ellos.
- Buscar hacia la izquierda o volver al inicio de
nums2. Solo cuentan los valores a la derecha, y el arreglo no vuelve al inicio.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Next Greater Element I?
La solución con pila monótona se ejecuta en O(n + m) de tiempo, donde n es la longitud de nums2 y m la de nums1. Cada valor de nums2 se apila y se desapila como máximo una vez, y cada valor de nums1 requiere una consulta al mapa. El mapa y la pila usan O(n) de espacio. Recorrer hacia la derecha desde cada valor requiere O(n·m) de tiempo.
¿Qué es una pila monótona?
Es una pila cuyos valores permanecen ordenados de abajo hacia arriba, aquí en orden decreciente. Antes de insertar un nuevo valor, extraes todos los que romperían el orden, y ahí es donde se realiza el trabajo: cada valor extraído ha encontrado su primer valor mayor a la derecha. Resuelve problemas como el siguiente mayor, el siguiente menor y otros similares en tiempo lineal.
¿Por qué Next Greater Element I necesita un mapa hash?
El recorrido de la pila produce respuestas en el orden en que los valores salen de la pila, asociadas a los valores de nums2. La salida debe seguir el orden de nums1, donde los mismos valores se encuentran en otras posiciones. Como todos los valores son distintos, un mapa de valores a respuestas conecta los dos arreglos con una búsqueda de tiempo constante por valor.
¿Qué cambia si nums2 es circular?
Luego, la búsqueda de un valor mayor puede continuar desde el inicio del arreglo. Recorre la pila de la misma manera por todo el arreglo dos veces, usando el índice i % n para i desde 0 hasta 2n-1, y apila valores solo durante la primera vuelta. Los valores que siguen en la pila después de ambas vueltas no tienen ningún valor mayor en ninguna parte, así que su respuesta es -1.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def nextGreaterElement(nums1, nums2):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
Esperado
[8, -1, 6]