Leetcode 739 Daily Temperatures

Soru

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Örnek 1

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Örnek 2

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Örnek 3

Input: temperatures = [30,60,90]
Output: [1,1,0]

Çözüm

• Hava sıcaklıklarının bir listesi verildiğinde, her gün için daha sıcak bir sıcaklık görülene kadar kaç gün beklemeniz gerektiğini hesaplamanızı ister. Eğer bir gün için daha sıcak bir gün yoksa, sonuç 0 olmalıdır.
• Girdi: Günlük sıcaklıkları içeren bir tam sayı dizisi T.
• Çıktı: Her gün için daha sıcak bir gün görülene kadar geçecek gün sayısını içeren bir tam sayı dizisi.
• Bu problem genellikle bir yığın (stack) kullanılarak çözülür. Yığın, daha sıcak bir gün bulunana kadar bekleyen günlerin indekslerini saklar. Her gün için, yığında saklanan önceki günlerle karşılaştırılır ve eğer mevcut günün sıcaklığı daha yüksekse, yığındaki günler için daha sıcak bir gün bulunmuş olur ve bu günler yığından çıkarılır.
• Çalışma Mekanizması:
• Sonuç Dizisi ve Yığın İnitialize Edilmesi: Sonuç dizisi sıfırlarla başlatılır. Yığın, bekleyen günlerin indekslerini saklamak için kullanılır.
• Döngü ile İşlem: Her gün için, yığının en üstündeki gün ile mevcut günün sıcaklığı karşılaştırılır.
• Yığın Kontrolü ve Güncelleme: Eğer mevcut gün sıcaklığı, yığının en üstündeki günden yüksekse, bu gün için daha sıcak bir gün bulunmuş olur. Yığın güncellenir ve sonuç dizisine kaç gün beklediği yazılır.
• Mevcut Günün Ekleme: Her günün indeksi, daha sıcak bir gün bulunana kadar yığına eklenir.
• Sonuç Dönüşü: Tüm günler için işlem tamamlandığında, sonuç dizisi döndürülür.

Code

   class Solution:
    def dailyTemperatures(self, T):
        result = [0] * len(T)  # Sonuç dizisini sıfırlarla başlat
        stack = []  # İndeksleri saklamak için yığın kullan

        for i in range(len(T)):
            # Mevcut sıcaklık, yığında bekleyen günlerin sıcaklığından yüksekse
            while stack and T[i] > T[stack[-1]]:
                index = stack.pop()  # Daha sıcak bir gün bulunan günün indeksini al
                result[index] = i - index  # Kaç gün beklediğini hesapla ve sonuca yaz
            stack.append(i)  # Mevcut günün indeksini yığına ekle

        return result

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n sıcaklık dizisinin uzunluğudur. Her eleman için yığın işlemi en fazla bir kez gerçekleşir.
• Space complexity (Alan Karmaşıklığı) : O(n), en kötü durumda tüm günler yığına eklenir.