Daily Temperatures
Ardışık günlerden oluşan bir sıradaki her günün sıcaklığı veriliyor: temperatures[i], i. gündeki sıcaklıktır. Her gün için, daha sıcak bir gün gelene kadar kaç gün beklemeniz gerektiğini sayın. Daha sonra daha sıcak bir gün gelmezse, o gün için bekleme süresi 0 olur.
Aynı uzunlukta bir dizi döndürün; burada i. eleman, i. gün için bekleme süresidir.
Fonksiyon
- temperaturesinteger-array
- her günün sıcaklığı, sırayla
- Döndürürinteger-array
- her gün için, daha sıcak bir güne kadar kalan gün sayısı; böyle bir gün yoksa 0
Kısıtlar
1 ≤ temperatures.length ≤ 10430 ≤ temperatures[i] ≤ 100- Daha sıcak, kesinlikle daha yüksek demektir: sıcaklığın aynı olduğu daha sonraki bir gün sayılmaz.
Örnekler
- Girdi
- temperatures = [71, 69, 72, 70, 70, 75, 68]
- Çıktı
- [2, 1, 3, 2, 1, 0, 0]
- Açıklama
- 0. gün 71'dir ve sıcaklığın daha yüksek olduğu ilk gün, 72 ile 2. gündür; bu nedenle 2 gün bekler. 3. ve 4. günlerin ikisi de 70'tir: ikinci 70 daha sıcak olmadığı için 3. gün, 75 ile 5. güne kadar bekler; bu da 2 gündür. 75 veya 68'den sonraki hiçbir gün daha sıcak değildir, bu nedenle ikisi de 0 alır.
- Girdi
- temperatures = [40, 50, 60]
- Çıktı
- [1, 1, 0]
- Açıklama
- Her gün bir öncekinden daha sıcaktır, bu yüzden ilk iki günün her biri 1 gün bekler. Son günün ardından başka bir gün gelmediğinden sonuç 0 olur.
- Girdi
- temperatures = [64, 60, 58, 61]
- Çıktı
- [0, 2, 1, 0]
- Açıklama
- 64'ten sonra daha sıcak bir gün yok, bu yüzden sonraki günlerde sıcaklık yeniden yükselse de 0. gün 0 alır. 60 derece olan 1. gün, daha soğuk olan 58'i atlar ve 61'i görmek için 2 gün bekler.
Gönderirken +13 gizli test
Ek soru
Sıcaklıklar yalnızca 71 farklı değer alır; 30'dan 100'e kadar. Sıcaklığa göre indekslenmiş bir tablo, sağdan sola tek geçişte her güne nasıl yanıt verebilir ve bu geçişin maliyeti nedir?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Sıcak günlerin nadir olduğu durumlarda, her günden başlayarak ileriye doğru tarama yapmak gün başına 10^4 adıma kadar mal olabilir. Bunu tersine çevir: Günleri soldan sağa bir kez dolaş ve daha sıcak bir gün bekleyen günleri tut. Sıcak bir gün geldiğinde onlara ne olur?
Bekleme günleri en eskiden en yeniye doğru asla daha sıcak olmaz: daha yeni bir gün daha sıcak olsaydı, daha eski olanı zaten yanıtlamış olurdu. Bu yüzden beklemedeki en soğuk gün her zaman en yeni gündür ve bir yığın onları tam olarak bu sırada tutar.
- Gün indekslerinden oluşan bir yığın tutun. Her yeni gün için, yığının en üstündeki gün bugünden daha soğuk olduğu sürece onu yığından çıkarın ve bugünün indeksinden o günün indeksini çıkararak sonucu olarak kaydedin. Ardından bugünü yığına ekleyin. Sonunda yığında kalan günlerin değeri 0 olarak kalır.
Çözüm
Tek bir gün için yanıt, ileriye doğru taramadır; ancak her günden başlayan bir tarama aynı işi tekrarlar ve sıcak günler nadir olduğunda her tarama dizinin sonuna kadar sürer. Çözüm, sonraki günleri sormak yerine her günün önceki günleri yanıtlamasını sağlamaktır: sıcaklığa göre sıralı kalan ve hâlâ yanıt bekleyen indekslerden oluşan bir yığın, tüm yanıtları tek geçişte bulur.
Her günden ileri doğru tarayın
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Sorunun söylediğini yap. i. gün için i+1. güne, sonra i+2. güne ve böyle devam ederek bak; sıcaklığı kesin olarak daha yüksek olan ilk günde dur. j-i uzaklığı cevaptır. Böyle bir gün bulamadan sona ulaşırsan cevap 0 olarak kalır.
Bu yöntem doğrudur çünkü tarama sonraki günleri sırayla ziyaret eder; dolayısıyla karşılaştığı ilk daha sıcak gün, var olan ilk daha sıcak gündür. Tam o noktada durmak da önemlidir: devam eden bir tarama bunun yerine son daha sıcak günü kaydederdi.
Daha sıcak günler uzaktaysa veya hiç yoksa yavaştır. 10^4 günün tamamında sıcaklık aynıysa hiçbir tarama erken durmaz: 0. gün 9,999 günü kontrol eder, 1. gün 9,998 günü kontrol eder ve toplamda yaklaşık n²/2 = 5 × 10^7 karşılaştırma yapılır. Taramalar ayrıca örtüşür: 1. gün, 0. günün daha önce taradığı yolun neredeyse aynısını yürür ve bundan hiçbir şey öğrenmez.
Algoritma
- Her gün için bir giriş olacak şekilde sıfırlardan oluşan bir cevap dizisi oluştur.
- Her
igünü içini+1değerinden son güne kadarjdeğerlerini tara. temperatures[j] > temperatures[i]koşulunu sağlayan ilkjdeğerindej-ideğerini kaydet ve taramayı durdur.- Cevap dizisini döndür; taramada sonuç bulunmayan günler 0 değerini korur.
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 answerBekleme günlerinden oluşan monoton yığın
Sezgi
Soruyu tersine çevir. Her gün kendisinden sonra ne geldiğini sormak yerine, günleri bir kez dolaş ve her yeni günün, kendisinden daha soğuk olan önceki günlere yanıt olmasını sağla. Henüz yanıtı olmayan günleri, indeks olarak bir yığında tut. Bugün geldiğinde, bugün kadar sıcak olmayan bekleyen her gün ilk daha sıcak gününü bulmuş olur: bugünü. Her birini yığından çıkar ve yanıtı olarak today - day yaz. Ardından bugünü yığına ekle; artık o da kendisinden daha sıcak bir günü bekler.
[71, 69, 72, 70, 70, 75, 68] dizisini dolaşalım. 0. gün (71) yığına eklenir. 1. gün (69), 71'den daha sıcak olmadığı için en üste eklenir: yığında [0, 1] günleri bulunur. 2. gün (72), 1. günü (bekleme 1) ve ardından 0. günü (bekleme 2) yığından çıkarır ve kendisi yığına eklenir. 3. ve 4. günler (70 ve 70) yığına eklenir; ikinci 70 ilkini yığından çıkarmaz, çünkü eşit sıcaklık daha sıcak değildir. 5. gün (75), 4. günü (bekleme 1), 3. günü (bekleme 2) ve 2. günü (bekleme 3) yığından çıkarır. 6. gün (68) yığına eklenir. 5. ve 6. günler turun sonunda hâlâ beklediğinden, değerleri 0 olarak kalır. Yanıt [2, 1, 3, 2, 1, 0, 0] olur.
Neden yalnızca en üstteki önemlidir: yığındaki sıcaklıklar alttan üste doğru hiçbir zaman artmaz. Bir gün, üzerindeki kendisinden daha soğuk tüm günler yığından çıkarıldıktan sonra eklenir; dolayısıyla altındaki her şey en az onun kadar sıcaktır. Bugün en üsttekinden daha sıcak değilse, onun altındakilerin hiçbirinden de daha sıcak değildir ve yığından çıkarmayı bırakabilirsin. Bir gün, ilk daha sıcak gün ortaya çıkar çıkmaz yığından çıkar; bu nedenle kaydettiğin bekleme süresi en sıcak güne değil, ilk daha sıcak güne kadardır.
Yığın sıcaklıkları değil, indeksleri tutar; çünkü yanıt bir uzaklıktır ve yanıtın hangi girdisini dolduracağını bilmen gerekir. Sıcaklığı temperatures[day] ile oku. Her gün yığına bir kez eklenir ve en fazla bir kez çıkarılır; bu nedenle tüm turdaki çıkarmaların toplamı en fazla n olur ve bir günde çok sayıda çıkarma yapılabilse de toplam süre O(n)'dir.
Algoritma
- Sıfırlardan oluşan bir cevap dizisi ve boş bir indeks yığını oluşturun.
- Her
todaygünü için, yığının en üstündeki güntodaygününden daha soğuk olduğu sürece, onu yığından çıkarın ve cevabınıtodayeksi o günün indeksi olarak ayarlayın. todaygününü yığına ekleyin.- Döngüden sonra, yığında kalan günlerin daha sıcak bir günü yoktur ve değerleri 0 olarak kalır. Cevap dizisini döndürün.
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
Tuzaklar ve uç durumlar
Yığın döngüsü birkaç satırdan oluşur; hatalar karşılaştırmada ve yığının ne tuttuğunda gizlidir.
>yerine>=durumunda eleman çıkarmak. Aynı sıcaklığa sahip bir gün daha sıcak değildir.[71, 69, 72, 70, 70, 75, 68]dizisinde 3. gün, ikinci 70 için 1 gün değil, 75 için 2 gün bekler.- İndisler yerine sıcaklıkları yığına eklemek. Yanıt, gün cinsinden bir mesafedir; bunu hesaplamak ve hangi girdinin doldurulacağını bilmek için indise ihtiyacın var.
whilegereken yerdeifkullanmak. Tek bir sıcak gün, bekleyen birçok günün yanıtını aynı anda verebilir: ilk örnekteki 75, üç güne yanıt verir.- Daha sıcak sıcaklığı veya daha sıcak günün indisini döndürmek. Çıktı, kaç gün bekleyeceğindir:
j-i. - Yığında kalan günlerin yanıtını ayarlamadan bırakmak. Yanıtları 0'dır; C dilinde yanıtı
callocile ayır veya doldur, çünkümallocile ayrılan bellek çöp değerler içerir. - İleri doğru taramanın ilk daha sıcak günü geçmesine izin vermek.
breakolmadan, ilk daha sıcak gün yerine sonuncusunu kaydeder.
Sıkça sorulan sorular4
Günlük Sıcaklıklar'ın zaman karmaşıklığı nedir?
Monotonik yığın çözümü O(n) zamanda çalışır ve O(n) ek alan kullanır. Her gün yığına bir kez eklenir ve en fazla bir kez çıkarılır; bu nedenle iç döngü, tüm tarama boyunca en fazla n kez çalışır. Her günden başlayarak ileriye doğru tarama yapmak O(n²) zaman alır; daha sıcak bir günün olmadığı 10^4 gün için yaklaşık 5 × 10^7 karşılaştırma gerekir.
Yığın neden sıcaklıklar yerine indisleri saklar?
Bir gün için yanıt bir mesafedir: today - day; bu yüzden günün konumuna ihtiyacın var. Dizin ayrıca gün yığından çıkarıldığında yanıt dizisinin hangi öğesini dolduracağını da söyler. Sıcaklık tek bir erişimle temperatures[day] olarak alınabilir; bu yüzden onu da saklamak hiçbir şey kazandırmaz.
Günlük Sıcaklıklar yığın kullanılmadan çözülebilir mi?
Evet. Son günden ilk güne doğru ilerle ve i günü için j = i+1 noktasından başla. j günü daha sıcak olmadığı sürece, j gününü yanıtlayan güne, yani j + answer[j] gününe atla; answer[j] 0 ise daha sıcak bir gün yoktur ve i günü de 0 alır. Bu atlamalar yanıt olamayacak tüm günleri atlar, her gün en fazla bir kez atlanır ve yanıt dizisi dışında bellek kullanmadan süre O(n) olarak kalır.
Günlük Sıcaklıklar, Sonraki Daha Büyük Eleman ile nasıl ilişkilidir?
Her konum için sorulan soru aynıdır: sağdaki bir sonraki daha büyük değeri bul. Next Greater Element bu değeri döndürür; Daily Temperatures ise aradaki mesafeyi döndürür, bu yüzden yığında indeksler tutulur. Daha küçük bir değerde eleman çıkarmak üzere tersine çevrilen aynı monoton yığın, bir sonraki daha küçük eleman sorularını da yanıtlar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def dailyTemperatures(temperatures):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
temperatures = [71, 69, 72, 70, 70, 75, 68]
Beklenen
[2, 1, 3, 2, 1, 0, 0]