Daily Temperatures

Q: ¿Cuál es la complejidad temporal de Daily Temperatures?

La solución con pila monótona se ejecuta en tiempo O(n) y usa O(n) de espacio adicional. Cada día se apila una vez y se desapila como máximo una vez, así que el bucle interno se ejecuta como máximo n veces en todo el recorrido. Recorrer hacia adelante desde cada día toma O(n²) de tiempo, aproximadamente 5 × 10^7 comparaciones para 10^4 días sin ningún día más cálido.

Q: ¿Por qué la pila almacena índices en lugar de temperaturas?

La respuesta para un día es una distancia, today - day , así que necesitas la posición del día. El índice también te indica qué entrada del arreglo de respuestas debes completar cuando se extrae el día. La temperatura está a una consulta de distancia con temperatures[day] , así que almacenarla también no aporta nada.

MedioPila monótona

+10

Obtienes la temperatura de cada día en una serie de días: temperatures[i] es la temperatura del día i. Para cada día, cuenta cuántos días tienes que esperar después de ese día hasta que llegue un día estrictamente más cálido. Si no llega ningún día más cálido después, la espera para ese día es 0.

Devuelve un array de la misma longitud en el que la entrada i es la espera para el día i.

Función

dailyTemperatures(temperatures: integer-array) → integer-array

temperaturesinteger-array: la temperatura de cada día, en orden
Devuelveinteger-array: para cada día, el número de días que faltan hasta uno más cálido, o 0 si no llega ninguno

Restricciones

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Más cálido significa estrictamente más alto: un día posterior con la misma temperatura no cuenta.

Ejemplos

Entrada: temperatures = [71, 69, 72, 70, 70, 75, 68]
Salida: [2, 1, 3, 2, 1, 0, 0]
Explicación: El día 0 es 71 y el primer día más cálido es el día 2 con 72, así que espera 2 días. Los días 3 y 4 son ambos 70: el segundo 70 no es más cálido, así que el día 3 espera hasta el día 5 con 75, lo que son 2 días. Después de 75 o 68 no hay ningún día más cálido, así que ambos obtienen 0.

+13 pruebas ocultas al enviar

Para ir más allá

Las temperaturas solo toman 71 valores, del 30 al 100. ¿Cómo podría una tabla indexada por temperatura responder cada día en una sola pasada de derecha a izquierda, y cuánto cuesta esa pasada?

Solución

Para un día, la respuesta es un recorrido hacia adelante, pero hacer un recorrido desde cada día repite el mismo trabajo, y cuando los días cálidos son poco frecuentes, cada recorrido llega hasta el final del array. La solución es hacer que cada día responda a los días anteriores en vez de preguntar por los posteriores: una pila de índices que todavía están esperando y que se mantiene ordenada por temperatura permite obtener todas las respuestas en una sola pasada.

Avanza desde cada día

Correcto, pero no termina con las pruebas más grandes

Intuición

Haz lo que dice el enunciado. Para el día i, mira el día i+1, después i+2, y así sucesivamente, y detente en el primer día cuya temperatura sea estrictamente más alta. La distancia j-i es la respuesta. Si llegas al final sin encontrar ninguno, la respuesta sigue siendo 0.

Es correcto porque el recorrido visita los días posteriores en orden, así que el primer día más cálido que encuentra es el primer día más cálido que existe. También es importante detenerse justo ahí: un recorrido que continuara registraría el último día más cálido en su lugar.

Es lento cuando los días más cálidos están muy lejos o no existen. Si los 10^4 días tienen la misma temperatura, ningún recorrido se detiene antes de tiempo: el día 0 revisa 9,999 días, el día 1 revisa 9,998, y el total es aproximadamente n²/2 = 5 × 10^7 comparaciones. Los recorridos también se solapan: el día 1 recorre casi exactamente el mismo terreno que ya recorrió el día 0 y no aprende nada de ello.

Algoritmo

Crea un array de respuestas con ceros, una entrada por día.
Para cada día i, recorre j desde i+1 hasta el último día.
En el primer j para el que temperatures[j] > temperatures[i], guarda j-i y detén el recorrido.
Devuelve el array de respuestas; los días para los que el recorrido no encontró nada conservan el 0.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # the first warmer day, so stop here
                break
    return answer

Pila monótona de días de espera

Intuición

Invierte la pregunta. En lugar de preguntar cada día qué viene después, recorre los días una vez y deja que cada nuevo día responda por los días anteriores a los que supera. Mantén en una pila, como índices, los días que aún no tienen respuesta. Cuando llega el día de hoy, todos los días en espera que son más fríos que hoy han encontrado su primer día más cálido: hoy. Saca cada uno y escribe today - day como su respuesta. Después, añade hoy a la pila, donde esperará su propio día más cálido.

Recorre [71, 69, 72, 70, 70, 75, 68]. Se añade el día 0 (71) a la pila. El día 1 (69) no es más cálido que 71, así que se añade encima: la pila contiene los días [0, 1]. El día 2 (72) saca el día 1 (espera 1) y después el día 0 (espera 2), y se añade a la pila. Se añaden los días 3 y 4 (70 y 70); el segundo 70 no saca el primero, porque ser igual no es ser más cálido. El día 5 (75) saca el día 4 (espera 1), el día 3 (espera 2) y el día 2 (espera 3). Se añade el día 6 (68) a la pila. Los días 5 y 6 siguen en espera al final, así que conservan el valor 0. La respuesta es [2, 1, 3, 2, 1, 0, 0].

Por qué solo importa el elemento superior: las temperaturas de la pila nunca aumentan de abajo hacia arriba. Un día se añade solo después de que se hayan sacado todos los días más fríos que tenía encima, así que todo lo que hay debajo es al menos igual de cálido. Si hoy no es más cálido que el elemento superior, tampoco es más cálido que nada de lo que hay debajo, y puedes dejar de sacar elementos. Un día sale de la pila en cuanto aparece el primer día más cálido, así que la espera que registras es hasta el primer día más cálido, no hasta el más cálido de todos.

La pila contiene índices, no temperaturas, porque la respuesta es una distancia y porque necesitas saber qué elemento de la respuesta rellenar. Lee la temperatura con temperatures[day]. Cada día se añade una vez y se saca como máximo una vez, así que todas las extracciones a lo largo del recorrido suman como máximo n, y el tiempo total es O(n), aunque un día pueda sacar muchos elementos.

Algoritmo

Crea un arreglo de respuestas lleno de ceros y una pila vacía de índices.
Para cada día today, mientras que el día en la parte superior de la pila sea más frío que hoy, sácalo de la pila y establece su respuesta como today menos su índice.
Apila today.
Después del bucle, los días que todavía están en la pila no tienen un día más cálido y conservan el valor 0. Devuelve el arreglo de respuestas.

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    waiting = []  # indices of days with no warmer day yet, colder toward the top
    for today, temp in enumerate(temperatures):
        # Today is the first warmer day for every colder day on top of the stack.
        while waiting and temperatures[waiting[-1]] < temp:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    # Days still waiting never get a warmer day and keep their 0.
    return answer

Errores comunes y casos límite

El bucle de la pila ocupa unas pocas líneas; los errores se esconden en la comparación y en lo que contiene la pila.

Desapilar con >= en lugar de >. Un día con la misma temperatura no es más cálido. En [71, 69, 72, 70, 70, 75, 68], el día 3 espera 2 días hasta el 75, no 1 día hasta el segundo 70.
Apilar las temperaturas en lugar de los índices. La respuesta es una distancia en días, y necesitas el índice para calcularla y saber qué entrada completar.
Usar if cuando necesitas while. Un día cálido puede responder de una vez por muchos días de espera: el 75 del primer ejemplo responde por tres.
Devolver la temperatura más cálida o el índice del día más cálido. La salida indica cuántos días esperas: j-i.
Dejar sin asignar las respuestas de los días que siguen en la pila. Su respuesta es 0; en C, reserva la respuesta con calloc o complétala, porque la memoria de malloc contiene basura.
Dejar que el recorrido hacia delante pase del primer día más cálido. Sin break, registra el último día más cálido en lugar del primero.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Daily Temperatures?

La solución con pila monótona se ejecuta en tiempo O(n) y usa O(n) de espacio adicional. Cada día se apila una vez y se desapila como máximo una vez, así que el bucle interno se ejecuta como máximo n veces en todo el recorrido. Recorrer hacia adelante desde cada día toma O(n²) de tiempo, aproximadamente 5 × 10^7 comparaciones para 10^4 días sin ningún día más cálido.

¿Por qué la pila almacena índices en lugar de temperaturas?

La respuesta para un día es una distancia, today - day, así que necesitas la posición del día. El índice también te indica qué entrada del arreglo de respuestas debes completar cuando se extrae el día. La temperatura está a una consulta de distancia con temperatures[day], así que almacenarla también no aporta nada.

¿Se puede resolver Daily Temperatures sin una pila?

Sí. Recorre los días desde el último hasta el primero y, para el día i, empieza en j = i+1. Mientras el día j no sea más cálido, salta al día que responde j, j + answer[j]; si answer[j] es 0, no existe ningún día más cálido y el día i también obtiene 0. Los saltos omiten todos los días que no pueden ser la respuesta, cada día se omite como máximo una vez y el tiempo se mantiene en O(n) sin usar memoria aparte del array de respuestas.

¿Qué relación hay entre Daily Temperatures y Next Greater Element?

Es la misma pregunta para cada posición: encuentra el siguiente valor mayor a la derecha. Next Greater Element devuelve ese valor; Daily Temperatures devuelve a qué distancia está, por eso la pila guarda índices. La misma pila monótona, invertida para desapilar cuando encuentra un valor menor, también responde preguntas sobre el siguiente elemento menor.

Python

def dailyTemperatures(temperatures):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

temperatures = [71, 69, 72, 70, 70, 75, 68]

Esperado

[2, 1, 3, 2, 1, 0, 0]