Daily Temperatures
temperatures[i], i. gündeki sıcaklıktır. Her gün için, ondan sonra daha sıcak bir gün gelene kadar kaç gün beklediğini say; daha sonra daha sıcak bir gün gelmiyorsa 0 kullan. Aynı uzunlukta, i. öğesi i. gün için bekleme süresini gösteren bir dizi döndür.
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 geçen gün sayısı ya da böyle bir gün gelmezse 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), 72 için 2 gün bekler. 3. gün (70), 4. gündeki eşit 70'i atlar ve 75 için 2 gün bekler. 75 veya 68'den sonra hiçbir sıcaklık daha yüksek olmadığından her ikisi de 0 alır.
- Girdi
- temperatures = [40, 50, 60]
- Çıktı
- [1, 1, 0]
- Açıklama
- Her gün bir önceki günden daha sıcaktır; bu nedenle ilk iki günün her biri 1 gün bekler, son gün ise 0 alır.
- Girdi
- temperatures = [64, 60, 58, 61]
- Çıktı
- [0, 2, 1, 0]
- Açıklama
- 64'ten sonraki hiçbir gün daha sıcak değil, bu yüzden sonraki günlerde sıcaklık yeniden yükselse de 0. gün 0 alır. 60 derecedeki 1. gün, daha soğuk olan 58'i atlar ve 61 için 2 gün bekler.
Ek soru
Sıcaklıklar yalnızca 71 değer alır: 30 ile 100 arası. Sıcaklığa göre indekslenen bir tablo, sağdan sola tek geçişte her güne nasıl yanıt verebilir ve bunun maliyeti ne olur?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Daha sıcak günlerin seyrek olduğu durumlarda, her günden ileriye doğru tarama yapmak gün başına 10^4 adıma kadar mal olabilir. 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 hiçbir zaman daha sıcak olmaz: daha yeni bir gün daha sıcak olsaydı, daha eski güne çoktan yanıt vermiş olurdu. Bu nedenle bekleyen en soğuk gün her zaman en yeni gündür ve bir yığın bu sırayı tam olarak korur.
Gün indekslerinden oluşan bir yığın tut. 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 ve bugünün indeksinden onun indeksini çıkararak sonucu olarak kaydet. Ardından bugünü yığına ekle. En sonda yığında kalan günlerin sonucu 0 olur.
Çözüm
Her günden ileriye doğru tarama işi tekrarlar ve sıcak günler nadir olduğunda her tarama sonuna kadar sürer. Bunun yerine, günleri bir kez dolaş ve her yeni günün, sıcaklığı daha yüksek olduğu önceki günleri yanıtlamasına izin ver. Hâlâ yanıt bekleyen günler, sıcaklıkları alttan üste doğru hiç artmayan bir yığında durur; böylece tüm yanıtlar tek geçişte bulunur.
Her günden ileriye doğru tara
Doğru, ama en büyük testlerde bitmiyor
Sezgi
i. gün için i+1, i+2 günlerini ve sonrasını kontrol et ve kesin olarak daha sıcak olan ilk j gününde dur. Yanıt j-i olur; tarama sona ulaşırsa 0 olur. Sırayla taramak, karşılaştığın ilk daha sıcak günün oradaki ilk gün olmasını sağlar.
10^4 günün tamamı aynı sıcaklıktaysa hiçbir tarama erken durmaz: yaklaşık n²/2 = 5 × 10^7 karşılaştırma yapılır ve 1. gün, 0. günün zaten katettiği yolun neredeyse aynısını kateder.
Algoritma
- Her gün için bir giriş içeren, sıfırlardan oluşan bir cevap dizisi oluşturun.
- Her
igünü içinjdeğerinii+1gününden son güne kadar tarayın. temperatures[j] > temperatures[i]koşulunu sağlayan ilkjiçinj-ideğerini kaydedin ve taramayı durdurun.- Cevap dizisini döndürün; taramada hiçbir şey bulunamayan günler 0 olarak kalır.
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 monotonik yığın
Sezgi
Henüz yanıtı olmayan günleri indeksler olarak bir yığında tut. Bugün geldiğinde, bugünden daha soğuk olan bekleyen günleri yığından çıkar: bugün, onlar için ilk daha sıcak gündür; dolayısıyla yanıtları today - day olur. Ardından bugünü yığına ekle.
Yalnızca en üstteki elemanı kontrol etmen yeterlidir. Bir gün yığına ancak üzerindeki daha soğuk günlerin tümü çıkarıldıktan sonra eklenir; bu nedenle yığındaki sıcaklıklar alttan üste doğru hiçbir zaman artmaz. Bugün en üsttekinden daha sıcak değilse, altındaki hiçbir günden de daha sıcak değildir ve çıkarmayı durdurursun. İlk örnekte, 5. gün (75), 4., 3. ve 2. günleri sırasıyla 1, 2 ve 3 günlük beklemelerle yığından çıkarırken, ikinci 70 ilk günü hiçbir zaman çıkarmadı; çünkü eşit sıcaklık daha sıcak değildir.
Her gün yığına bir kez eklenir ve en fazla bir kez çıkarılır; bu nedenle çıkarma işlemlerinin toplamı en fazla n olur: Bir gün birçok günü çıkarabilse de süre O(n) olur.
Algoritma
- Sıfırlardan oluşan bir yanıt dizisi ve boş bir indeks yığını oluştur.
- Her
todaygünü için, yığının en üstündeki gün bugünden daha soğuk olduğu sürece onu yığından çıkar ve yanıtınıtodayeksi o günün indeksi olarak ayarla. todaydeğerini yığına ekle.- Döngüden sonra yığında kalan günlerin daha sıcak bir günü yoktur ve yanıtları 0 olarak kalır. Yanıt dizisini döndür.
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
>=yerine>kullanıldığında eleman çıkarmak. İlk örnekte 3. gün, ikinci 70'i görmek için 1 gün bekler; oysa 75 için 2 gün beklemesi gerekir.- İndeksler yerine sıcaklıkları yığına eklemek. Böylece uzaklığı hesaplayamaz veya yanıtın hangi girişini dolduracağınızı belirleyemezsiniz.
whilegereken yerdeifkullanmak. Sıcak bir gün, bekleyen birçok günü yanıtlayabilir: ilk örnekte 75, üç günü yanıtlar.- Yığında kalan günlerin yanıtını ayarlamamak. Yanıtları 0'dır; C'de yanıt dizisini
callocile ayırın, çünkümallocbelleği çöp değerler içerir. - İleri yöndeki taramanın ilk daha sıcak günü geçmesine izin vermek.
breakolmadan bunun yerine son daha sıcak günü kaydeder.
Sıkça sorulan sorular3
Daily Temperatures algoritmasının zaman karmaşıklığı nedir?
Monotonik yığın çözümü O(n) zamanda ve O(n) ek alan kullanarak çalışır; çünkü her gün yığına bir kez eklenir ve en fazla bir kez çıkarılır. Her günden ileriye doğru tarama, daha sıcak bir gün bulunmadığında 104 gün için yaklaşık 5 × 10^7 karşılaştırma gerektirerek O(n²) zaman alır.
Günlük Sıcaklıklar problemi yığın kullanılmadan çözülebilir mi?
Evet. Yanıtları son günden geriye doğru doldur ve i günü için j = i+1 noktasından başla; j günü daha sıcak değilse, j gününün yanıtını veren gün olan j + answer[j] konumuna atla. answer[j] 0 ise i günü de 0 alır. Bu atlamalar, i günü için yanıt olamayacak günleri geçer: O(n) zaman, ek bellek yok.
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 ona kaç konum uzaklıkta olduğunu döndürür, bu yüzden yığın indeksleri tutar. Aynı yığın, daha küçük bir değerde eleman çıkaracak şekilde kullanıldığında, bir sonraki daha küçük elemanla ilgili soruları yanıtlar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def dailyTemperatures(temperatures):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
temperatures = [71, 69, 72, 70, 70, 75, 68]
Beklenen Çıktı
[2, 1, 3, 2, 1, 0, 0]