Wawancara Koding: Bagaimana Cara Menyelesaikan Sliding Window Maximum dengan Monotonic Deque?

Masalah dan Skenario yang Berlaku

Diberikan sebuah array bilangan bulat nums dan ukuran jendela k, jendela pertama mencakup indeks 0 hingga k - 1. Geser jendela satu posisi ke kanan setiap kali dan kembalikan nilai maksimum dari setiap jendela. Batasannya adalah 1 <= nums.length <= 100000 dan 1 <= k <= nums.length. Sebagai contoh:

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
result = [3, 3, 5, 5, 6, 7]

Targetnya adalah waktu O(n) dan ruang bantu O(k), tidak termasuk array keluaran. Masalah standar menjamin array tidak kosong dan k yang valid. Jika API produksi harus menerima array kosong atau k yang tidak valid, tentukan nilai kembalian atau exception secara terpisah alih-alih mencampur perilaku yang tidak ditentukan ke dalam pembuktian algoritma.

Berbagai sumber persiapan wawancara berbahasa Mandarin dan Inggris yang diterbitkan pada tahun 2026 masih menggunakan Sliding Window Maximum sebagai latihan monotonic deque langsung dan meminta kandidat untuk menjelaskan elemen depan, indeks yang kedaluwarsa, penggusuran elemen belakang, dan kompleksitas teramortisasi. Sebuah solusi publik berbahasa Mandarin yang diterbitkan pada tahun 2026 juga membandingkan pendekatan brute-force dan deque. Keterampilan intinya adalah penalaran algoritma dan struktur data umum, sehingga kategori yang benar adalah coding; contoh TypeScript tidak menjadikannya pertanyaan frontend.

Apa yang Sedang Dinilai oleh Pewawancara

Pertama, apakah Anda dapat mengenali strukturnya: satu elemen masuk dan satu elemen keluar pada setiap pergeseran, sementara nilai ekstrem harus tetap tersedia? Brute force memindai ulang k - 1 elemen yang dipakai bersama oleh jendela yang berdekatan. Monotonic deque hanya menyimpan indeks yang masih bisa menjadi nilai maksimum saat ini atau di masa mendatang.

Kedua, dapatkah Anda menjelaskan mengapa deque menyimpan indeks alih-alih nilainya saja? Kedaluwarsa bergantung pada posisi, dan nilai yang sama dapat berasal dari posisi yang berbeda. Tanpa indeks, Anda tidak dapat mengetahui secara andal apakah nilai maksimum di bagian depan telah meninggalkan jendela.

Ketiga, dapatkah Anda membuktikan bahwa elemen belakang boleh dihapus secara permanen? Jika j < i dan nums[j] <= nums[i], elemen yang lebih baru berukuran setidaknya sama besar dan kedaluwarsa lebih lambat. Kapan pun keduanya berada dalam satu jendela, elemen yang lebih lama tidak akan pernah menang. Ini adalah argumen dominasi, bukan sekadar cara untuk membuat deque terlihat terurut.

Terakhir, kompleksitas memerlukan analisis teramortisasi. Satu iterasi dapat menghapus beberapa indeks, sehingga satu iterasi tunggal tidak secara ketat bernilai O(1). Namun, setiap indeks masuk satu kali dan keluar paling banyak satu kali dari salah satu ujung, sehingga seluruh operasi deque jika digabungkan membutuhkan waktu O(n).

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah ukuran jendela tetap? Ukurannya tetap pada k; jendela variabel membutuhkan aturan kedaluwarsa dan kontrak kueri yang disesuaikan.
• Bisakah array kosong? Batasan standar mengecualikannya; API yang diperluas harus secara eksplisit mengembalikan array kosong atau menolak input tersebut.
• Apakah k dijamin valid? Deskripsi masalah menyatakan ya; implementasi contoh tetap memvalidasinya saat runtime untuk mencegah panjang yang tidak valid atau akses di luar batas.
• Bisakah nilai berulang atau bernilai negatif? Ya. Algoritma ini hanya bergantung pada perbandingan dan indeks, bukan kepositifan atau keunikan nilai.
• Haruskah nilai yang sama mempertahankan indeks yang lebih baru atau yang lebih lama? Keduanya menghasilkan nilai maksimum yang benar. Solusi ini menghapus nilai sama yang lebih lama dan mempertahankan indeks yang kedaluwarsa lebih lambat.
• Haruskah ruang bantu benar-benar O(k)? Ya. Array JavaScript yang hanya memajukan pointer kepala tanpa mereklamasi slot lama dapat menahan penyimpanan O(n); solusi ini menggunakan circular buffer dengan kapasitas k.
• Apakah kita mengembalikan nilai atau indeks maksimum? Masalah utama mengembalikan nilai. Jika indeks yang diminta, kembalikan indeks depan dan tentukan aturan pemutus seri (tie rule) untuk nilai maksimum duplikat.
• Bolehkah input dimodifikasi? Tidak. Implementasi hanya membaca nums.

Kerangka Jawaban 30 Detik

“Saya akan menyimpan indeks kandidat dalam sebuah deque. Indeks meningkat dari depan ke belakang, sementara nilainya menurun secara ketat. Pada indeks i, pertama-tama saya menghapus indeks yang kedaluwarsa dari depan. Kemudian saya menghapus indeks dari belakang selama nilainya kurang dari atau sama dengan nums[i], karena elemen baru tersebut setidaknya sama besar dan kedaluwarsa lebih lambat. Setelah memasukkan i, nilai depan adalah jawabannya setelah jendela penuh pertama terbentuk. Setiap indeks dimasukkan satu kali dan dihapus paling banyak satu kali, sehingga total waktunya adalah O(n). Deque berisi paling banyak k indeks, menghasilkan ruang bantu O(k).”

Pembahasan Mendalam Langkah demi Langkah

Langkah 1: Gunakan pendekatan dasar untuk menemukan pekerjaan yang berulang.

Ketika n dan k mendekati 100000, brute force dapat melakukan sekitar 10^10 perbandingan. Heap adalah jawaban perantara yang berguna, tetapi struktur ini mempertahankan prioritas di antara semua entri. Masalah ini hanya membaca nilai maksimum, sehingga kandidat yang lebih lama yang didominasi oleh entri yang lebih baru tidak memiliki nilai di masa depan.

Langkah 2: Nyatakan aturan dominasi secara tepat.

Misalkan j < i dan nums[j] <= nums[i]. Di setiap jendela mendatang yang berisi kedua indeks, nilai pada j tidak dapat melebihi nilai pada i. Seiring jendela bergerak ke kanan, j juga kedaluwarsa sebelum i. Oleh karena itu, sejak i tiba, j tidak akan pernah bisa menjadi nilai maksimum jendela lagi dan dapat dihapus secara permanen dari himpunan kandidat.

Menggunakan kondisi kurang-dari-atau-sama-dengan dalam penghapusan hanya mempertahankan indeks terbaru untuk nilai yang sama dan membuat nilai deque menurun secara ketat. Menghapus hanya nilai yang strictly lebih kecil juga benar, tetapi nilainya hanya akan non-increasing dan beberapa kandidat yang sama akan tetap ada. Pembuktian dan kode harus menggunakan strategi yang sama.

Langkah 3: Pertahankan empat invarian yang dapat diperiksa.

Setelah memproses indeks i:

1. Indeks dalam deque meningkat secara ketat dan mengikuti urutan kedatangan.
2. Setiap indeks yang disimpan berada dalam rentang saat ini [i - k + 1, i].
3. Nilai array yang bersesuaian menurun secara ketat dari depan ke belakang.
4. Setiap indeks yang dihapus dari jendela saat ini memiliki kandidat yang lebih baru dan tidak lebih kecil yang tersisa di sepanjang rantai dominasinya.

Tiga properti pertama menjadikan elemen depan sebagai kandidat terbesar yang dipertahankan. Properti keempat menunjukkan bahwa tidak ada elemen yang dibuang yang bisa menjadi nilai maksimum sebenarnya. Bersama-sama, mereka menetapkan bahwa elemen depan mewakili seluruh jendela, bukan sekadar elemen terbesar di dalam deque.

Langkah 4: Implementasikan circular deque yang benar-benar menggunakan ruang O(k).

export function maxSlidingWindow(
  nums: readonly number[],
  k: number,
): number[] {
  if (!Number.isInteger(k) || k < 1 || k > nums.length) {
    throw new RangeError("k must be an integer between 1 and nums.length");
  }

  const deque = new Int32Array(k);
  let head = 0;
  let size = 0;
  const result: number[] = [];

  for (let i = 0; i < nums.length; i += 1) {
    while (size > 0 && deque[head] <= i - k) {
      head = (head + 1) % k;
      size -= 1;
    }

    while (size > 0) {
      const back = (head + size - 1) % k;
      if (nums[deque[back]] > nums[i]) break;
      size -= 1;
    }

    deque[(head + size) % k] = i;
    size += 1;

    if (i >= k - 1) {
      result.push(nums[deque[head]]);
    }
  }

  return result;
}

Circular buffer memiliki tepat k slot. Entri yang kedaluwarsa dihapus sebelum setiap push, sehingga jendela saat ini berisi paling banyak k - 1 indeks yang valid sebelum menulis indeks baru; operasi push tidak dapat menimpa bagian depan. Int32Array dapat menyimpan indeks hingga batas maksimum yang dinyatakan yaitu 100000. Jika suatu varian mengizinkan indeks di luar rentang 32-bit, gunakan array numerik biasa atau sesuaikan kontrak input.

Langkah 5: Buktikan bahwa setiap nilai yang dilaporkan adalah nilai maksimum jendela yang sebenarnya.

Deque dimulai dalam keadaan kosong, sehingga semua invarian terpenuhi. Ketika indeks baru tiba, penghapusan dari depan hanya membuang elemen di luar jendela saat ini. Penghapusan dari belakang menerapkan aturan dominasi: setiap elemen yang dihapus digantikan oleh indeks yang lebih baru dan tidak lebih kecil i. Memasukkan i mempertahankan indeks yang meningkat dan nilai yang menurun secara ketat.

Jendela lengkap pertama terbentuk pada i = k - 1. Sejak saat itu, elemen depan selalu berada di dalam jendela. Nilai deque yang menurun secara ketat membuatnya lebih besar daripada setiap kandidat lain yang dipertahankan, sementara rantai dominasi memastikan bahwa setiap elemen yang tidak dipertahankan tidak lebih besar dari beberapa kandidat yang dipertahankan. Oleh karena itu nums[deque[head]] adalah nilai maksimum saat ini. Induksi pada semua i membuktikan bahwa semua n - k + 1 keluaran adalah benar.

Langkah 6: Telusuri nilai duplikat dan batas kedaluwarsa.

Untuk contoh tersebut, setiap entri di bawah ini adalah index:value:

i=0  [0:1]                  no full window yet
i=1  [1:3]                  3 dominates 1
i=2  [1:3, 2:-1]            output 3
i=3  [1:3, 2:-1, 3:-3]      output 3
i=4  [4:5]                  1 expires; 5 dominates -1 and -3; output 5
i=5  [4:5, 5:3]             output 5
i=6  [6:6]                  6 dominates 5 and 3; output 6
i=7  [7:7]                  7 dominates 6; output 7

Untuk [4, 4, 4] dengan k = 2, angka 4 kedua menghapus angka 4 pertama, dan angka 4 ketiga menghapus angka 4 kedua. Deque selalu berisi indeks terbaru, sementara kedua jendela tetap mengembalikan nilai 4. Kasus ini memeriksa kondisi nilai yang sama dan menunjukkan mengapa menyimpan nilai saja tidak dapat melacak kedaluwarsa dengan benar.

Langkah 7: Berikan kompleksitas teramortisasi secara akurat.

Dua loop while tidak melipatgandakan kompleksitas menjadi O(nk). Setiap indeks dimasukkan satu kali dan tidak pernah kembali setelah dihapus, sehingga semua penghapusan depan dan belakang bersama-sama terjadi paling banyak n kali. Total waktunya adalah O(n). Circular deque menyimpan paling banyak k indeks, sehingga ruang bantunya adalah O(k). Output memiliki n - k + 1 entri dan biasanya dikecualikan dari analisis ruang bantu.

Langkah 8: Gunakan naive oracle untuk pengujian diferensial.

Kasus uji tetap harus mencakup k = 1, k = n, semua nilai sama, array strictly increasing dan decreasing, semua nilai negatif, dan contoh campuran standar. Array kosong dan k = 0 adalah input yang tidak valid dan harus melempar RangeError. Kemudian buat array acak pendek dan k acak yang valid, lalu bandingkan setiap keluaran dengan implementasi naif yang memindai setiap jendela. Pemeriksaan acak harus memverifikasi panjang hasil dan nilai untuk setiap jendela.

Untuk n yang sangat kecil atau jendela tunggal, pemindaian brute-force lebih pendek dan lebih mudah ditinjau. Jika bahasa pemrograman menyediakan deque yang andal, lebih disukai menggunakan kontainer standar tersebut. Circular buffer dihadirkan di sini agar batas penyimpanan fisik implementasi TypeScript cocok dengan analisis O(k)-nya.

Contoh Jawaban yang Kuat

“Brute force memindai k elemen untuk setiap jendela, yang menghasilkan O(nk) dalam kasus terburuk. Saya akan mempertahankan sebuah monotonic deque indeks. Indeks meningkat dalam urutan kedatangan, sementara nilainya menurun secara ketat dari depan ke belakang.

Pada indeks i, pertama-tama saya menghapus setiap indeks depan yang kurang dari atau sama dengan i - k, karena indeks tersebut telah kedaluwarsa. Kemudian saya menghapus indeks dari belakang selama nilainya kurang dari atau sama dengan nums[i]. Elemen baru tersebut setidaknya sama besar dan meninggalkan jendela lebih lambat, sehingga elemen-elemen yang lebih lama tersebut tidak akan pernah bisa menjadi nilai maksimum lagi. Saya memasukkan i, dan setelah i >= k - 1, elemen depan memberikan nilai maksimum saat ini.

Kebenaran algoritma ini berasal dari dua fakta: penghapusan depan berada di luar jendela, dan setiap penghapusan belakang memiliki pengganti yang lebih baru dan tidak lebih kecil yang bertahan lebih lama. Karena nilai yang dipertahankan menurun, kandidat tersisa terbesar berada di bagian depan. Setiap indeks masuk satu kali dan keluar paling banyak satu kali, sehingga total waktunya adalah O(n). Deque menyimpan paling banyak k indeks, menghasilkan ruang bantu O(k). Saya akan menguji k = 1, k = n, nilai duplikat, array monoton, dan angka negatif, lalu membandingkan kasus acak terhadap oracle brute-force.”

Kesalahan Umum

• Hanya menyimpan nilai dalam deque → Nilai yang sama tidak dapat dibedakan saat kedaluwarsa → Simpan indeks dan baca nilai dari array.
• Mempertahankan nilai yang menurun tetapi tidak pernah menghapus elemen depan yang kedaluwarsa → Nilai maksimum lama terus muncul setelah meninggalkan jendela → Bersihkan bagian depan menggunakan i - k pada setiap iterasi.
• Menggunakan < i - k sebagai pengujian kedaluwarsa → Indeks yang sama dengan i - k sudah berada di sebelah kiri jendela → Gunakan kurang-dari-atau-sama-dengan.
• Menyebut loop while bersarang sebagai O(nk) → Suatu indeks tidak dapat dihapus berulang kali → Gunakan fakta bahwa setiap indeks masuk dan keluar paling banyak satu kali.
• Menggunakan shift() dan mengklaim penghapusan waktu konstan → JavaScript dapat menggeser elemen array saat penghapusan di bagian depan → Gunakan deque standar, pointer kepala, atau circular buffer.
• Memajukan pointer kepala tanpa mereklamasi penyimpanan dan mengklaim ruang O(k) → Array pendukung masih dapat tumbuh hingga O(n) → Gunakan penyimpanan sirkular dengan kapasitas tetap k.
• Ketidakcocokan aturan nilai sama dan pembuktian → Invarian strictly decreasing dan non-increasing menjadi tercampur → Nyatakan bahwa solusi ini menghapus nilai yang lebih lama dengan kurang-dari-atau-sama-dengan.
• Menempatkan nilai saja dalam heap → Lazy deletion tetap tidak dapat mengidentifikasi entri yang kedaluwarsa → Pendekatan heap juga harus menyimpan indeks.
• Hanya menguji contoh standar → Kesalahan batas pada k = 1, duplikat, dan array yang menurun tetap tersembunyi → Tambahkan batasan tetap dan oracle teracak.

Pertanyaan Lanjutan dan Tanggapan

Lanjutan 1: Mengapa aman untuk menghapus nilai sama yang lebih lama?

Indeks yang lebih baru memiliki nilai yang sama dan pasti kedaluwarsa lebih lambat. Di setiap jendela yang berisi keduanya, salah satu indeks akan memberikan nilai maksimum yang sama. Indeks yang lebih lama keluar terlebih dahulu dan tidak dapat memperoleh kesempatan kembali setelah indeks yang lebih baru kedaluwarsa. Oleh karena itu, hanya mempertahankan indeks yang lebih baru adalah aman dan memperpendek deque.

Lanjutan 2: Bagaimana jika hasilnya harus menyertakan kemunculan pertama dari setiap nilai maksimum?

Jangan hapus nilai sama yang lebih lama. Hapus hanya nilai yang strictly lebih kecil dari belakang, sehingga nilai deque menjadi non-increasing. Bagian depan kemudian mempertahankan nilai maksimum paling awal di jendela saat ini. Jika hasilnya memerlukan kemunculan terakhir, pertahankan penghapusan kurang-dari-atau-sama-dengan pada solusi ini. Aturan pemutus serinya berubah, tetapi batas O(n) tidak berubah.

Lanjutan 3: Mengapa tidak menggunakan max heap?

Heap adalah solusi cepat yang valid jika menyimpan nilai beserta indeks dan melakukan lazy deletion. Entri kedaluwarsa yang tidak berada di puncak tetap teralokasi, sehingga binary heap biasa dapat membengkak hingga ruang O(n) dan membutuhkan waktu O(n log n). Indexed heap dengan penghapusan arbitrer dapat mencapai waktu O(n log k) dan ruang O(k), tetapi lebih rumit. Dalam wawancara, heap bisa menjadi jawaban perantara yang berguna sebelum mengoptimalkannya ke monotonic deque.

Lanjutan 4: Bagaimana jika setiap jendela membutuhkan nilai maksimum dan minimumnya sekaligus?

Pertahankan dua deque independen: satu dengan nilai menurun untuk maksimum dan satu dengan nilai meningkat untuk minimum. Setiap indeks tetap masuk dan keluar dari setiap deque paling banyak satu kali, sehingga total waktu tetap O(n) dan ruang bantu tetap O(k).

Lanjutan 5: Bagaimana jika ukuran jendela berubah pada setiap kueri?

Jika kedua batas masih hanya bergerak ke kanan, gunakan batas kiri saat ini untuk menghapus indeks yang kedaluwarsa dan monotonic deque tetap berfungsi. Jika jendela dapat meluas ke arah kiri, kandidat yang telah dibuang secara permanen dapat masuk kembali ke dalam rentang dan tidak dapat dipulihkan. Gunakan balanced tree, segment tree, atau struktur range-maximum-query offline sesuai dengan pola pembaruan dan kueri.

Lanjutan 6: Bagaimana Anda memproses aliran tak terbatas (infinite stream) secara daring (online)?

Tetapkan nomor urut yang terus meningkat untuk setiap kedatangan elemen, terapkan langkah kedaluwarsa dan penghapusan belakang yang sama, lalu keluarkan nilai depan setelah elemen ke-k dan pada setiap kedatangan berikutnya. Simpan paling banyak k kandidat indeks dan nilai, sehingga memori tidak bergantung pada total panjang aliran data. Kedatangan yang tidak berurutan juga akan memerlukan jendela event-time, watermark, dan kebijakan late-data; hal itu berada di luar model array terurut dari masalah ini.

Lanjutan 7: Bagaimana pola ini diterapkan pada dynamic programming terbatas (bounded dynamic programming)?

Untuk rekursi di mana status saat ini sama dengan biayanya sendiri ditambah nilai maksimum dari k status sebelumnya, pertahankan deque yang diurutkan berdasarkan nilai DP. Bagian depan memasok nilai maksimum transisi, sementara kedaluwarsa tetap bergantung pada indeks. Target perbandingan berubah dari nums[i] menjadi dp[i], tetapi pembuktiannya tetap bergantung pada status yang lebih baru dan tidak lebih kecil yang mendominasi status yang lebih lama.