Daily Temperatures
temperatures[i] adalah suhu pada hari i. Untuk setiap hari, hitung berapa hari kamu harus menunggu setelah hari itu sampai hari yang suhunya lebih tinggi tiba, atau 0 jika tidak ada hari yang lebih panas setelahnya. Kembalikan array dengan panjang yang sama, dengan entri i sebagai waktu tunggu untuk hari i.
Fungsi
- temperaturesinteger-array
- suhu setiap hari, secara berurutan
- Mengembalikaninteger-array
- untuk setiap hari, jumlah hari hingga hari yang lebih hangat, atau 0 jika tidak ada hari yang lebih hangat
Batasan
1 ≤ temperatures.length ≤ 10430 ≤ temperatures[i] ≤ 100- Lebih hangat berarti benar-benar lebih tinggi: hari berikutnya dengan suhu yang sama tidak dihitung.
Contoh
- Input
- temperatures = [71, 69, 72, 70, 70, 75, 68]
- Output
- [2, 1, 3, 2, 1, 0, 0]
- Penjelasan
- Hari ke-0 (71) menunggu 2 hari untuk 72. Hari ke-3 (70) melewati 70 yang sama pada hari ke-4 dan menunggu 2 hari untuk 75. Tidak ada suhu setelah 75 atau 68 yang lebih hangat, jadi keduanya mendapat 0.
- Input
- temperatures = [40, 50, 60]
- Output
- [1, 1, 0]
- Penjelasan
- Setiap hari lebih hangat daripada hari sebelumnya, jadi dua hari pertama masing-masing menunggu 1 hari, dan hari terakhir mendapat 0.
- Input
- temperatures = [64, 60, 58, 61]
- Output
- [0, 2, 1, 0]
- Penjelasan
- Tidak ada suhu setelah 64 yang lebih hangat, jadi hari 0 mendapat 0 meskipun suhu pada hari-hari setelahnya naik lagi. Hari 1 dengan suhu 60 melewati suhu 58 yang lebih dingin dan menunggu 2 hari untuk suhu 61.
Pertanyaan lanjutan
Suhu hanya memiliki 71 nilai, dari 30 hingga 100. Bagaimana tabel yang diindeks berdasarkan suhu dapat menjawab setiap hari dalam satu kali lintasan dari kanan ke kiri, dan berapa biayanya?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Memindai ke depan dari setiap hari dapat memerlukan hingga 10^4 langkah per hari saat hari yang lebih hangat jarang terjadi. Lakukan sebaliknya: telusuri hari-hari sekali dari kiri ke kanan dan simpan hari-hari yang masih menunggu hari yang lebih hangat. Apa yang terjadi pada hari-hari itu saat hari yang panas tiba?
Hari-hari yang menunggu tidak pernah menjadi lebih hangat dari yang paling lama hingga yang paling baru: jika hari yang lebih baru lebih hangat, hari itu pasti sudah menjawab hari yang lebih lama. Jadi, hari menunggu yang paling dingin selalu yang paling baru, dan stack mempertahankan urutan tersebut dengan tepat.
Simpan tumpukan indeks hari. Untuk setiap hari baru, selama hari yang berada di puncak tumpukan lebih dingin daripada hari ini, keluarkan hari itu dari tumpukan dan simpan indeks hari ini dikurangi indeksnya sebagai jawabannya. Lalu, masukkan hari ini ke tumpukan. Hari-hari yang tersisa di tumpukan pada akhirnya tetap bernilai 0.
Solusi
Penelusuran maju dari setiap hari mengulang pekerjaan, dan saat hari-hari hangat jarang terjadi, setiap penelusuran berjalan sampai akhir. Sebaliknya, telusuri hari-hari itu sekali dan biarkan setiap hari baru menjawab hari-hari sebelumnya yang berhasil dikalahkannya. Hari-hari yang masih menunggu berada di sebuah stack dengan suhu yang tidak pernah meningkat dari bawah ke atas, sehingga semua jawaban didapat dalam satu kali lintasan.
Pindai ke depan dari setiap hari
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Untuk hari i, periksa hari i+1, i+2, dan seterusnya, lalu berhenti pada hari pertama j yang suhunya lebih hangat. Jawabannya adalah j-i, atau 0 jika pemindaian mencapai akhir. Memindai secara berurutan memastikan hari pertama yang lebih hangat yang kamu temui adalah hari pertama yang ada.
Jika suhu pada semua 10^4 hari sama, pemindaian tidak akan berhenti lebih awal: sekitar n²/2 = 5 × 10^7 perbandingan, dan hari ke-1 menelusuri hampir area yang sama dengan yang sudah ditelusuri hari ke-0.
Algoritma
- Buat array jawaban yang berisi nol, satu entri untuk setiap hari.
- Untuk setiap hari
i, pindaijdarii+1hingga hari terakhir. - Pada
jpertama dengantemperatures[j] > temperatures[i], simpanj-idan hentikan pemindaian. - Kembalikan array jawaban; hari yang pemindaiannya tidak menemukan apa pun tetap bernilai 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 answerStack monotonik untuk hari penantian
Intuisi
Simpan hari yang belum memiliki jawaban di stack sebagai indeks. Saat hari ini tiba, keluarkan setiap hari yang masih menunggu dan suhunya lebih dingin daripada hari ini: hari ini adalah hari pertama yang lebih hangat baginya, jadi jawabannya adalah today - day. Lalu, masukkan hari ini.
Kamu hanya perlu memeriksa bagian atas. Sebuah hari dimasukkan hanya setelah semua hari yang lebih dingin di atasnya dikeluarkan, jadi suhu pada stack tidak pernah meningkat dari bawah ke atas. Jika hari ini tidak lebih hangat daripada bagian atas, hari ini juga tidak lebih hangat daripada hari mana pun di bawahnya, jadi berhentilah mengeluarkan hari. Pada contoh pertama, hari ke-5 (75) mengeluarkan hari ke-4, ke-3, dan ke-2 dengan waktu tunggu 1, 2, dan 3, sedangkan 70 yang kedua tidak pernah mengeluarkan yang pertama, karena suhu yang sama tidak lebih hangat.
Setiap hari dimasukkan sekali dan dikeluarkan paling banyak sekali, jadi total pengeluaran paling banyak n: waktu O(n), meskipun satu hari dapat mengeluarkan banyak hari.
Algoritma
- Buat array jawaban yang berisi nol dan stack indeks kosong.
- Untuk setiap hari
today, selama hari yang berada di puncak stack lebih dingin daripada hari ini, keluarkan hari tersebut dari stack dan atur jawabannya menjaditodaydikurangi indeksnya. - Masukkan
todayke dalam stack. - Setelah perulangan, hari-hari yang masih berada di stack tidak memiliki hari yang lebih hangat dan tetap bernilai 0. Kembalikan array jawaban.
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
Jebakan dan kasus tepi
- Mengeluarkan nilai saat memakai
>=, bukan>. Pada contoh pertama, hari ke-3 menunggu 1 hari untuk nilai 70 kedua, bukan 2 hari untuk 75. - Memasukkan suhu, bukan indeks. Dengan begitu, kamu tidak dapat menghitung jarak atau mengetahui entri jawaban mana yang harus diisi.
- Menggunakan
ifsaat kamu membutuhkanwhile. Satu hari yang hangat dapat menjawab banyak hari yang masih menunggu: nilai 75 pada contoh pertama menjawab tiga hari. - Membiarkan hari-hari yang masih ada di stack tidak diisi. Jawabannya adalah 0. Di C, alokasikan jawaban dengan
calloc, karena memorimallocberisi data sampah. - Membiarkan pemindaian maju melewati hari pertama yang lebih hangat. Tanpa
break, pemindaian akan mencatat hari terakhir yang lebih hangat.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu Daily Temperatures?
Solusi monotonic stack berjalan dalam waktu O(n) dan menggunakan ruang tambahan O(n), karena setiap hari dimasukkan sekali dan dikeluarkan paling banyak sekali. Memindai ke depan dari setiap hari membutuhkan waktu O(n²), sekitar 5 × 10^7 perbandingan untuk 10^4 hari tanpa hari yang lebih hangat.
Bisakah Daily Temperatures diselesaikan tanpa stack?
Ya. Isi jawaban mulai dari hari terakhir ke belakang, dan untuk hari i mulai dari j = i+1; selama hari j tidak lebih hangat, lompat ke j + answer[j], yaitu hari yang menjadi jawaban untuk j. Jika answer[j] adalah 0, hari i juga mendapat 0. Lompatan ini melewati hari-hari yang tidak bisa menjadi jawaban untuk i: waktu O(n), tanpa memori tambahan.
Bagaimana hubungan Daily Temperatures dengan Next Greater Element?
Pertanyaan yang sama diajukan untuk setiap posisi: temukan nilai lebih besar berikutnya di sebelah kanan. Next Greater Element mengembalikan nilai tersebut; Daily Temperatures mengembalikan jaraknya, itulah sebabnya stack menyimpan indeks. Stack yang sama, dengan kondisi pop dibalik saat menemukan nilai yang lebih kecil, menjawab pertanyaan tentang elemen lebih kecil berikutnya.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def dailyTemperatures(temperatures):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
temperatures = [71, 69, 72, 70, 70, 75, 68]
Output yang diharapkan
[2, 1, 3, 2, 1, 0, 0]