Daily Temperatures

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

La solución con pila monótona se ejecuta en O(n) y usa O(n) de espacio adicional, porque cada día se inserta una vez y se extrae como máximo una vez. Recorrer hacia adelante desde cada día toma O(n²) , unas 5 × 10^7 comparaciones para 10^4 días sin ningún día más cálido.

MedioPila monótona

+10

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, o 0 si no llega ningún día más cálido después. Devuelve un array de la misma longitud, donde la entrada i es la espera correspondiente al 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 hasta un día más cálido, o 0 si no llega ninguno

Restricciones

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Más cálido significa una temperatura estrictamente superior: 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 (71) espera 2 días a que llegue el 72. El día 3 (70) se salta el 70 igual del día 4 y espera 2 días hasta el 75. Nada después del 75 ni del 68 es más cálido, así que ambos reciben 0.

Para ir más allá

Las temperaturas solo pueden tomar 71 valores, del 30 al 100. ¿Cómo podría una tabla indexada por temperatura responder todos los días en una pasada de derecha a izquierda, y a qué costo?

Solución

Un recorrido hacia adelante desde cada día repite trabajo, y cuando los días cálidos son poco frecuentes, cada recorrido llega hasta el final. En su lugar, recorre los días una sola vez y deja que cada día nuevo responda a los días anteriores a los que supera. Los días que aún esperan están en una pila cuyas temperaturas nunca aumentan de abajo hacia arriba, así que todas las respuestas se obtienen en una sola pasada.

Avanza de un día a otro

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

Intuición

Para el día i, comprueba los días i+1, i+2 y así sucesivamente, y detente en el primer día estrictamente más cálido j. La respuesta es j-i, o 0 si el recorrido llega al final. Recorrerlos en orden hace que el primer día más cálido que encuentres sea el primero que existe.

Si los 10^4 días tienen la misma temperatura, ningún recorrido se detiene antes de tiempo: aproximadamente n²/2 = 5 × 10^7 comparaciones, y el día 1 recorre casi el mismo terreno que el día 0 ya recorrió.

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 donde temperatures[j] > temperatures[i], guarda j-i y detén el recorrido.
Devuelve el array de respuestas; los días cuyo 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

Guarda en una pila, como índices, los días que todavía no tienen respuesta. Cuando llega el día de hoy, saca de la pila todos los días pendientes que sean más fríos que hoy: hoy es el primer día más cálido para ellos, así que su respuesta es today - day. Después, añade hoy a la pila.

Solo hace falta comprobar la cima. Un día se añade a la pila únicamente después de sacar todos los días más fríos que estaban por encima, así que las temperaturas de la pila nunca aumentan de abajo hacia arriba. Si hoy no es más cálido que el día de la cima, tampoco es más cálido que ninguno de los que están debajo, y dejas de sacar días. En el primer ejemplo, el día 5 (75) saca los días 4, 3 y 2, con esperas de 1, 2 y 3, mientras que el segundo 70 nunca sacó el primero, ya que una temperatura igual no es más cálida.

Cada día se añade a la pila una vez y se saca como máximo una vez, así que el total de extracciones es como máximo n: tiempo O(n), aunque un día pueda sacar muchos.

Algoritmo

Crea un arreglo de respuestas lleno de ceros y una pila vacía de índices.
Para cada día today, mientras 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 en today menos su índice.
Coloca today en la pila.
Después del bucle, los días que siguen 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

Quitar elementos con >= en lugar de >. En el primer ejemplo, el día 3 espera 1 día para el segundo 70 en lugar de 2 días para el 75.
Insertar temperaturas en lugar de índices. Así, no puedes calcular la distancia ni saber qué entrada de la respuesta rellenar.
Usar if cuando necesitas while. Un día cálido puede responder por muchos días de espera: el 75 del primer ejemplo responde por tres.
Dejar sin establecer los días que aún están en la pila. Su respuesta es 0; en C, asigna la respuesta con calloc, porque la memoria de malloc contiene basura.
Dejar que el recorrido hacia delante pase del primer día más cálido. Sin el break, registra el último día más cálido en su lugar.

Preguntas frecuentes3

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

La solución con pila monótona se ejecuta en O(n) y usa O(n) de espacio adicional, porque cada día se inserta una vez y se extrae como máximo una vez. Recorrer hacia adelante desde cada día toma O(n²), unas 5 × 10^7 comparaciones para 10^4 días sin ningún día más cálido.

¿Se puede resolver Temperaturas diarias sin una pila?

Sí. Completa las respuestas desde el último día hacia atrás y, para el día i, empieza en j = i+1; mientras el día j no sea más cálido, salta a j + answer[j], el día que responde a j. Si answer[j] es 0, el día i también obtiene 0. Los saltos omiten los días que no pueden responder para i: tiempo O(n), sin memoria adicional.

¿Qué relación tiene Daily Temperatures con 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, invertida para desapilar cuando aparece un valor menor, responde preguntas sobre el siguiente elemento menor.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

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

Salida Esperada

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