Maksimum Sliding Window dengan Deque
Mempertahankan nilai ekstrem window dalam O(n)
Maksimum Sliding Window dengan Deque adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Maksimum Jendela Geser
Diberikan sebuah larik dan ukuran jendela k, Anda ingin mencari maksimum dari setiap jendela saat bergeser ke kanan. Cara naif memerlukan O(n kali k).
Jaminan yang Lebih Cepat
Dengan antrean dua ujung monoton, Anda dapat menjawab setiap jendela dalam total waktu O(n) dengan memindai larik hanya satu kali.
Simpan Indeks Lagi
Simpan indeks dalam antrean dua ujung, bukan nilai. Indeks memungkinkan Anda memeriksa apakah bagian depan sudah bergeser keluar dari jendela saat ini.
from collections import deque
dq = deque()
res = []Pertahankan Urutan Menurun
Antrean dua ujung tetap menurun berdasarkan nilai dari depan ke belakang, sehingga indeks di bagian depan selalu menunjuk ke nilai maksimum jendela.
Buang Bagian Belakang yang Lebih Kecil
Sebelum menambahkan indeks i, keluarkan elemen dari belakang selama values tersebut lebih kecil, karena elemen-elemen itu tidak mungkin menjadi maksimum di masa depan.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Tambahkan Indeks Baru
Setelah membersihkan bagian belakang yang lebih lemah, append indeks saat ini. Urutan antrean dua ujung tetap benar untuk langkah-langkah berikutnya.
dq.append(i)Keluarkan Bagian Depan yang Kedaluwarsa
Jika indeks di bagian depan berada di luar jendela, keluarkan dengan popleft. Jendela berukuran k dimulai pada indeks i dikurangi k ditambah 1.
if dq[0] <= i - k:
dq.popleft()Catat Setiap Nilai Maksimum
Setelah jendela penuh pertama terbentuk pada indeks k dikurangi 1, bagian depan antrean dua ujung menyimpan jawaban untuk setiap posisi berikutnya.
if i >= k - 1:
res.append(nums[dq[0]])Perhatikan Urutan Pengeluaran
Keluarkan bagian depan yang kedaluwarsa sebelum membaca jawaban. Jika tidak, Anda mungkin melaporkan nilai maksimum yang sudah keluar dari jendela.
Mengapa Waktunya Linear
Setiap indeks ditambahkan dan dihapus paling banyak satu kali, sehingga pekerjaan antrean dua ujung memerlukan waktu teramortisasi O(1) per langkah dan O(n) secara keseluruhan.
Minimum Jendela, Gagasan Sama
Untuk mencari minimum jendela geser, pertahankan antrean dua ujung dalam urutan meningkat. Cukup balikkan perbandingan saat memangkas bagian belakang.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Pemeriksaan Singkat
Dalam masalah maksimum jendela geser, apa yang disimpan di bagian depan antrean dua ujung monoton?
Ringkasan: Antrean Dua Ujung Unggul pada Jendela
Anda mempertahankan antrean dua ujung menurun yang berisi indeks: pangkas bagian belakang yang kecil, keluarkan bagian depan yang kedaluwarsa, lalu baca bagian depan untuk mendapatkan maksimum setiap jendela dalam O(n). 🏆
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Maksimum Sliding Window dengan Deque” gratis?
Ya — teks lengkap “Maksimum Sliding Window dengan Deque” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Maksimum Sliding Window dengan Deque”?
Mempertahankan nilai ekstrem window dalam O(n) Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Maksimum Sliding Window dengan Deque” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Stack untuk Mencocokkan Kurung
- Stack Monoton: Elemen Lebih Besar Berikutnya
- Queue dan collections.deque
- Maksimum Sliding Window dengan Deque