Maksimum Sliding Window dengan Deque
Mempertahankan nilai ekstrem window dalam O(n)
Maksimum Sliding Window dengan Deque adalah pelajaran Coding Interview Prep 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep 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). 🏆
Belajar Coding Interview Prep dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 90
- Pelajaran
- 360
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 Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Maksimum Sliding Window dengan Deque”?
Mempertahankan nilai ekstrem window dalam O(n) Kamu berlatih Coding Interview Prep 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 Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep 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 Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep 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