Maksimum Tetingkap Gelongsor dengan Deque
Kekalkan ekstremum tetingkap dalam O(n).
Maksimum Tetingkap Gelongsor dengan Deque ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Maksimum Tetingkap Gelongsor
Diberikan tatasusunan dan saiz tetingkap k, Anda mahu nilai maksimum bagi setiap tetingkap semasa ia bergerak ke kanan. Melakukannya secara naif mengambil masa O(n darab k).
Janji yang Lebih Pantas
Dengan baris gilir dua hujung monoton, Anda boleh mendapatkan jawapan bagi setiap tetingkap dalam jumlah masa O(n), dengan mengimbas tatasusunan sekali sahaja.
Simpan Indeks Sekali Lagi
Simpan indeks dalam baris gilir dua hujung, bukan nilai. Indeks membolehkan Anda menyemak sama ada bahagian hadapan sudah tergelincir keluar dari tetingkap semasa.
from collections import deque
dq = deque()
res = []Pastikan Susunan Menurun
Baris gilir dua hujung kekal menurun mengikut nilai dari hadapan ke belakang, jadi indeks di hadapan sentiasa menunjuk kepada maksimum tetingkap.
Buang Ekor yang Lebih Kecil
Sebelum menambah indeks i, keluarkan dari belakang selagi nilai-nilai tersebut lebih kecil, kerana nilai itu tidak mungkin menjadi maksimum pada masa akan datang.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Tambah Indeks Baharu
Selepas membuang ekor yang lebih lemah, append indeks semasa. Susunan baris gilir dua hujung kekal betul untuk langkah seterusnya.
dq.append(i)Keluarkan Hadapan yang Tidak Lagi Sah
Jika indeks di hadapan berada di luar tetingkap, lakukan popleft terhadapnya. Tetingkap bersaiz k bermula pada indeks i tolak k tambah satu.
if dq[0] <= i - k:
dq.popleft()Catat Setiap Maksimum
Apabila tetingkap penuh yang pertama terbentuk pada indeks k tolak satu, bahagian hadapan baris gilir dua hujung memegang jawapan untuk setiap kedudukan selepas itu.
if i >= k - 1:
res.append(nums[dq[0]])Perhatikan Urutan Pengeluaran
Keluarkan bahagian hadapan yang tidak lagi sah sebelum membaca jawapan. Jika tidak, Anda mungkin melaporkan maksimum yang sudah keluar dari tetingkap.
Mengapa Masa Linear Kekal
Setiap indeks ditambah dan dikeluarkan paling banyak sekali, jadi kerja baris gilir dua hujung ialah O(1) secara teramortisasi bagi setiap langkah dan O(n) secara keseluruhan.
Tetingkap Minimum, Idea Sama
Untuk minimum tetingkap gelongsor, pastikan baris gilir dua hujung menaik pula. Hanya terbalikkan perbandingan apabila memangkas bahagian belakang.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Semakan Pantas
Dalam masalah maksimum tetingkap gelongsor, apakah yang dipegang oleh bahagian hadapan baris gilir dua hujung monoton?
Ulang Kaji: Baris Gilir Dua Hujung Menguasai Tetingkap
Anda mengekalkan baris gilir dua hujung indeks yang menurun: pangkas ekor kecil, keluarkan bahagian hadapan yang tidak lagi sah, dan baca bahagian hadapan untuk mendapatkan maksimum setiap tetingkap dalam O(n). 🏆
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Maksimum Tetingkap Gelongsor dengan Deque” percuma?
Ya — teks penuh “Maksimum Tetingkap Gelongsor dengan Deque” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Maksimum Tetingkap Gelongsor dengan Deque”?
Kekalkan ekstremum tetingkap dalam O(n). Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Maksimum Tetingkap Gelongsor dengan Deque” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Timbunan untuk Padanan Kurungan
- Timbunan Monotonik: Elemen Lebih Besar Seterusnya
- Baris Gilir dan collections.deque
- Maksimum Tetingkap Gelongsor dengan Deque