Temu Duga Pengekodan: Bagaimana Anda Menyelesaikan Sliding Window Maximum dengan Monotonic Deque?

Masalah dan Senario yang Berkenaan

Diberikan tatasusunan integer nums dan saiz tetingkap k, tetingkap pertama merangkumi indeks 0 hingga k - 1. Gerakkan tetingkap satu kedudukan ke kanan pada satu masa dan kembalikan nilai maksimum bagi setiap tetingkap. Kekangannya ialah 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]

Sasarannya ialah masa O(n) dan ruang bantuan O(k), tidak termasuk tatasusunan output. Masalah standard menjamin tatasusunan tidak kosong dan k yang sah. Jika API pengeluaran mesti menerima tatasusunan kosong atau k yang tidak sah, tentukan nilai pulangan atau pengecualian secara berasingan dan bukannya mencampurkan tingkah laku yang tidak dinyatakan ke dalam pembuktian algoritma.

Pelbagai sumber persediaan temu duga berbahasa Cina dan Inggeris yang diterbitkan pada tahun 2026 masih menggunakan Sliding Window Maximum sebagai latihan monotonic deque secara langsung dan meminta calon menerangkan elemen hadapan, indeks luput, penyingkiran belakang, dan kerumitan terpelunasan. Penyelesaian awam berbahasa Cina yang diterbitkan pada tahun 2026 juga membandingkan pendekatan brute-force dan deque. Kemahiran teras ialah penaakulan algoritma dan struktur data umum, jadi kategori yang betul ialah coding; contoh TypeScript tidak menjadikannya soalan frontend.

Perkara yang Dinilai oleh Penemu Duga

Pertama, bolehkah anda mengecam strukturnya: satu elemen masuk dan satu keluar pada setiap pergerakan, manakala satu nilai ekstrem mesti kekal tersedia? Brute force mengimbas semula k - 1 elemen yang dikongsi oleh tetingkap bersebelahan. Monotonic deque hanya menyimpan indeks yang masih boleh menjadi maksimum semasa atau masa hadapan.

Kedua, bolehkah anda menerangkan mengapa deque menyimpan indeks dan bukannya nilai semata-mata? Kelupuputan bergantung pada kedudukan, dan nilai yang sama boleh datang daripada kedudukan berbeza. Tanpa indeks, anda tidak dapat memastikan secara andal sama ada nilai maksimum di hadapan telah meninggalkan tetingkap.

Ketiga, bolehkah anda membuktikan bahawa elemen belakang boleh dialih keluar secara kekal? Jika j < i dan nums[j] <= nums[i], elemen yang lebih baharu adalah sekurang-kurangnya sama besar dan luput lebih lewat. Setiap kali kedua-duanya berada dalam sesuatu tetingkap, elemen yang lebih lama tidak boleh menang. Ini ialah hujah dominasi, bukan sekadar cara untuk menjadikan deque kelihatan terisih.

Akhir sekali, kerumitan memerlukan analisis terpelunasan. Satu lelaran boleh mengalih keluar beberapa indeks, jadi lelaran individu tidak semestinya O(1). Walau bagaimanapun, setiap indeks masuk sekali dan keluar paling banyak sekali dari mana-mana hujung, jadi semua operasi deque bersama-sama mengambil masa O(n).

Soalan Penjelasan Sebelum Menjawab

• Adakah saiz tetingkap tetap? Ia ditetapkan pada k; tetingkap boleh ubah memerlukan peraturan kelupuputan dan kontrak pertanyaan yang disemak semula.
• Bolehkah tatasusunan menjadi kosong? Kekangan standard mengecualikannya; API yang diperluas harus secara eksplisit mengembalikan tatasusunan kosong atau menolak input tersebut.
• Adakah k dijamin sah? Masalah menyatakan ya; pelaksanaan contoh masih mengesahkannya semasa masa jalanan untuk mengelakkan panjang tidak sah atau akses luar batas.
• Bolehkah nilai berulang atau bernilai negatif? Ya. Algoritma ini hanya bergantung pada perbandingan dan indeks, bukan kepositifan atau keunikan.
• Patutkah nilai yang sama mengekalkan indeks yang lebih baharu atau lebih lama? Mana-mana satu menghasilkan maksimum yang betul. Penyelesaian ini mengalih keluar nilai sama yang lebih lama dan mengekalkan indeks yang luput lebih lewat.
• Adakah ruang bantuan benar-benar mesti O(k)? Ya. Tatasusunan JavaScript yang hanya memajukan penunjuk kepala tanpa menuntut semula slot lama boleh mengekalkan storan O(n); penyelesaian ini menggunakan penimbal pekeliling berkapasiti k.
• Adakah kita mengembalikan nilai atau indeks maksimum? Masalah utama mengembalikan nilai. Jika indeks diperlukan, kembalikan indeks hadapan dan tentukan peraturan pemutus seri untuk maksimum pendua.
• Bolehkah input diubah suai? Tidak. Pelaksanaan ini hanya membaca nums.

Rangka Jawapan 30 Saat

“Saya akan menyimpan indeks calon dalam satu deque. Indeks meningkat dari hadapan ke belakang, manakala nilainya menurun secara ketat. Pada indeks i, saya terlebih dahulu mengalih keluar indeks yang luput dari hadapan. Saya kemudian mengalih keluar indeks dari belakang selagi nilainya kurang daripada atau sama dengan nums[i], kerana elemen baharu adalah sekurang-kurangnya sama besar dan luput lebih lewat. Selepas memasukkan i, nilai hadapan ialah jawapannya sebaik sahaja tetingkap penuh pertama wujud. Setiap indeks dimasukkan sekali dan dialih keluar paling banyak sekali, jadi jumlah masa ialah O(n). Deque mengandungi paling banyak k indeks, memberikan ruang bantuan O(k).”

Perbincangan Terperinci Langkah demi Langkah

Langkah 1: Gunakan pendekatan asas untuk mengesan kerja berulang.

Apabila kedua-dua n dan k menghampiri 100000, brute force boleh melakukan kira-kira 10^10 perbandingan. Heap ialah jawapan perantaraan yang berguna, tetapi ia mengekalkan keutamaan dalam kalangan semua entri. Masalah ini hanya membaca nilai maksimum, jadi calon lebih lama yang didominasi oleh entri baharu tidak mempunyai nilai masa hadapan.

Langkah 2: Nyatakan peraturan dominasi dengan tepat.

Andaikan j < i dan nums[j] <= nums[i]. Dalam setiap tetingkap masa hadapan yang mengandungi kedua-dua indeks, nilai pada j tidak boleh melebihi nilai pada i. Apabila tetingkap bergerak ke kanan, j juga luput sebelum i. Oleh itu, dari saat i tiba, j tidak boleh menjadi maksimum tetingkap lagi dan boleh dialih keluar secara kekal daripada set calon.

Menggunakan kurang daripada atau sama dengan dalam syarat penyingkiran hanya mengekalkan indeks terbaharu bagi nilai yang sama dan menjadikan nilai deque menurun secara ketat. Mengalih keluar hanya nilai yang strictly lebih kecil juga betul, tetapi kemudian nilainya sekadar tidak meningkat (nonincreasing) dan berbilang calon yang sama akan kekal. Bukti dan kod mestilah menggunakan strategi yang sama.

Langkah 3: Kekalkan empat invarian yang boleh disemak.

Selepas memproses indeks i:

1. Indeks dalam deque meningkat secara ketat dan mengikut urutan ketibaan.
2. Setiap indeks yang disimpan terletak dalam julat semasa [i - k + 1, i].
3. Nilai tatasusunan yang sepadan menurun secara ketat dari hadapan ke belakang.
4. Setiap indeks yang dialih keluar daripada tetingkap semasa mempunyai calon terkemudian yang tidak lebih kecil yang kekal di sepanjang rantai dominasinya.

Tiga sifat pertama menjadikan bahagian hadapan sebagai calon terbesar yang dikekalkan. Sifat keempat menunjukkan bahawa tiada elemen yang dibuang boleh menjadi maksimum sebenar. Secara bersama, sifat-sifat ini membuktikan bahawa bahagian hadapan mewakili keseluruhan tetingkap, bukan sekadar elemen terbesar di dalam deque.

Langkah 4: Laksanakan 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;
}

Penimbal pekeliling mempunyai tepat k slot. Entri yang luput dialih keluar sebelum setiap operasi tolak (push), jadi tetingkap semasa mengandungi paling banyak k - 1 indeks yang sah sebelum menulis indeks baharu; operasi tolak tidak boleh menimpa bahagian hadapan. Int32Array boleh menyimpan indeks sehingga maksimum yang dinyatakan iaitu 100000. Jika varian membenarkan indeks di luar julat 32-bit, gunakan tatasusunan angka biasa atau semak semula kontrak input.

Langkah 5: Buktikan bahawa setiap nilai yang dilaporkan ialah maksimum tetingkap yang sebenar.

Deque bermula dalam keadaan kosong, jadi semua invarian dipenuhi. Apabila indeks baharu tiba, penyingkiran hadapan hanya membuang elemen di luar tetingkap semasa. Penyingkiran belakang menggunakan peraturan dominasi: setiap elemen yang dialih keluar digantikan oleh indeks yang lebih baharu dan tidak lebih kecil i. Menolak i mengekalkan indeks yang meningkat dan nilai yang menurun secara ketat.

Tetingkap lengkap pertama wujud pada i = k - 1. Sejak itu, bahagian hadapan sentiasa berada di dalam tetingkap. Nilai deque yang menurun secara ketat menjadikannya lebih besar daripada setiap calon lain yang dikekalkan, manakala rantai dominasi memastikan bahawa setiap elemen yang tidak dikekalkan adalah tidak lebih besar daripada beberapa calon yang dikekalkan. Oleh itu nums[deque[head]] ialah maksimum semasa. Aruhan ke atas semua i membuktikan bahawa semua n - k + 1 output adalah betul.

Langkah 6: Surih nilai pendua dan sempadan kelupuputan.

Untuk contoh tersebut, setiap entri di bawah ialah 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 mengalih keluar angka 4 pertama, dan angka 4 ketiga mengalih keluar angka 4 kedua. Deque sentiasa mengandungi indeks terbaharu, manakala kedua-dua tetingkap masih mengembalikan 4. Kes ini menyemak syarat nilai yang sama dan mendedahkan sebab menyimpan nilai sahaja tidak dapat menjejak kelupuputan dengan betul.

Langkah 7: Berikan kerumitan terpelunasan dengan tepat.

Dua gelung while tidak mendarabkan kerumitan kepada O(nk). Setiap indeks ditolak sekali dan tidak pernah kembali selepas dialih keluar, jadi semua penyingkiran hadapan dan belakang bersama-sama berlaku paling banyak n kali. Jumlah masa ialah O(n). Circular deque menyimpan paling banyak k indeks, jadi ruang bantuan ialah O(k). Output mempunyai n - k + 1 entri dan biasanya dikecualikan daripada analisis ruang bantuan.

Langkah 8: Gunakan naive oracle untuk ujian pembezaan.

Kes tetap harus merangkumi k = 1, k = n, semua nilai sama, tatasusunan yang meningkat dan menurun secara ketat, semua nilai negatif, dan contoh campuran standard. Tatasusunan kosong dan k = 0 ialah input yang tidak sah dan harus melontarkan RangeError. Kemudian jana tatasusunan rawak pendek dan k sah yang rawak, serta bandingkan setiap output dengan pelaksanaan naif yang mengimbas setiap tetingkap. Semakan rawak hendaklah mengesahkan panjang hasil dan nilai bagi setiap tetingkap.

Untuk n yang sangat kecil atau satu tetingkap tunggal, imbasan brute-force adalah lebih pendek dan lebih mudah disemak. Jika bahasa pengaturcaraan menyediakan deque yang andal, utamakan bekas standard tersebut. Penimbal pekeliling disertakan di sini supaya batas storan fizikal pelaksanaan TypeScript sepadan dengan analisis O(k)-nya.

Contoh Jawapan yang Mantap

“Brute force mengimbas k elemen untuk setiap tetingkap, iaitu O(nk) dalam kes terburuk. Saya akan mengekalkan satu monotonic deque bagi indeks. Indeks meningkat mengikut urutan ketibaan, manakala nilainya menurun secara ketat dari hadapan ke belakang.

Pada indeks i, saya terlebih dahulu mengalih keluar setiap indeks hadapan yang kurang daripada atau sama dengan i - k, kerana ia telah luput. Saya kemudian mengalih keluar indeks dari belakang selagi nilainya kurang daripada atau sama dengan nums[i]. Elemen baharu adalah sekurang-kurangnya sama besar dan meninggalkan tetingkap lebih lewat, jadi elemen lama tersebut tidak boleh menjadi maksimum lagi. Saya menolak i, dan sebaik sahaja i >= k - 1, bahagian hadapan memberikan nilai maksimum semasa.

Ketepatan terhasil daripada dua fakta: penyingkiran hadapan berada di luar tetingkap, dan setiap penyingkiran belakang mempunyai pengganti yang lebih baharu dan tidak lebih kecil yang bertahan lebih lama. Oleh kerana nilai yang dikekalkan menurun, calon terbesar yang tinggal berada di hadapan. Setiap indeks masuk sekali dan keluar paling banyak sekali, jadi jumlah masa ialah O(n). Deque menyimpan paling banyak k indeks, memberikan ruang bantuan O(k). Saya akan menguji k = 1, k = n, nilai pendua, tatasusunan monoton, dan nombor negatif, kemudian membandingkan kes rawak dengan oracle brute-force.”

Kesilapan Biasa

• Hanya menyimpan nilai dalam deque → Nilai yang sama tidak dapat dibezakan semasa luput → Simpan indeks dan baca nilai daripada tatasusunan.
• Mengekalkan nilai yang menurun tetapi tidak pernah mengalih keluar bahagian hadapan yang luput → Maksimum lama terus muncul selepas ia meninggalkan tetingkap → Bersihkan bahagian hadapan menggunakan i - k pada setiap lelaran.
• Menggunakan < i - k sebagai ujian kelupuputan → Indeks yang sama dengan i - k sudah berada di sebelah kiri tetingkap → Gunakan kurang daripada atau sama dengan.
• Memanggil gelung while bersarang sebagai O(nk) → Sesuatu indeks tidak boleh dialih keluar berulang kali → Gunakan fakta bahawa setiap indeks masuk dan keluar paling banyak sekali.
• Menggunakan shift() dan mendakwa penyingkiran masa malar → JavaScript mungkin menganjakkan elemen tatasusunan semasa pemadaman hadapan → Gunakan deque standard, penunjuk kepala, atau penimbal pekeliling.
• Memajukan penunjuk kepala tanpa menuntut semula storan dan mendakwa ruang O(k) → Tatasusunan sandaran masih boleh berkembang kepada O(n) → Gunakan storan pekeliling dengan kapasiti tetap k.
• Peraturan nilai sama dan bukti tidak sepadan → Invarian strictly decreasing dan nonincreasing menjadi bercampur → Nyatakan bahawa penyelesaian ini mengalih keluar nilai lebih lama dengan kurang daripada atau sama dengan.
• Meletakkan nilai sahaja dalam heap → Pemadaman malas masih tidak dapat mengenal pasti entri yang luput → Pendekatan heap mesti menyimpan indeks juga.
• Hanya menguji contoh standard → Ralat sempadan dalam k = 1, pendua, dan tatasusunan menurun kekal tersembunyi → Tambah sempadan tetap dan oracle rawak.

Soalan Susulan dan Maklum Balas

Susulan 1: Mengapakah selamat untuk mengalih keluar nilai sama yang lebih lama?

Indeks yang lebih baharu mempunyai nilai yang sama dan semestinya luput lebih lewat. Dalam setiap tetingkap yang mengandungi kedua-duanya, mana-mana indeks membekalkan maksimum yang sama. Indeks yang lebih lama keluar dahulu dan tidak boleh memperoleh peluang semula selepas indeks yang lebih baharu luput. Oleh itu, mengekalkan indeks yang lebih baharu sahaja adalah selamat dan memendekkan deque.

Susulan 2: Bagaimana jika hasilnya mesti menyertakan kemunculan pertama bagi setiap maksimum?

Jangan alih keluar nilai sama yang lebih lama. Alih keluar hanya nilai yang strictly lebih kecil dari belakang, menjadikan nilai deque tidak meningkat (nonincreasing). Bahagian hadapan kemudiannya mengekalkan maksimum terawal dalam tetingkap semasa. Jika hasilnya memerlukan kemunculan terakhir, kekalkan penyingkiran kurang daripada atau sama dengan dalam penyelesaian ini. Peraturan pemutus seri berubah, tetapi batas O(n) tidak berubah.

Susulan 3: Mengapa tidak menggunakan max heap?

Heap ialah penyelesaian pantas yang sah apabila ia menyimpan nilai beserta indeks dan melakukan pemadaman malas. Entri luput yang bukan di bahagian atas kekal diperuntukkan, jadi binary heap biasa boleh berkembang kepada ruang O(n) dan mengambil masa O(n log n). Indexed heap dengan pemadaman sewenang-wenangnya boleh mencapai masa O(n log k) dan ruang O(k), tetapi ia lebih rumit. Dalam temu duga, heap boleh menjadi jawapan perantaraan yang berguna sebelum mengoptimumkannya kepada monotonic deque.

Susulan 4: Bagaimana jika setiap tetingkap memerlukan kedua-dua nilai maksimum dan minimumnya?

Kekalkan dua deque bebas: satu dengan nilai menurun untuk maksimum dan satu dengan nilai meningkat untuk minimum. Setiap indeks masih masuk dan keluar daripada setiap deque paling banyak sekali, jadi jumlah masa kekal O(n) dan ruang bantuan kekal O(k).

Susulan 5: Bagaimana jika saiz tetingkap berubah pada setiap pertanyaan?

Jika kedua-dua sempadan masih hanya bergerak ke kanan, gunakan sempadan kiri semasa untuk mengalih keluar indeks yang luput dan monotonic deque masih berfungsi. Jika tetingkap boleh mengembang ke arah kiri, calon yang telah dibuang secara kekal mungkin memasuki semula julat dan tidak dapat dipulihkan. Gunakan pokok seimbang, pokok segmen, atau struktur pertanyaan julat maksimum luar talian (offline range-maximum-query) mengikut corak kemas kini dan pertanyaan.

Susulan 6: Bagaimanakah anda memproses strim tak terhingga (infinite stream) secara dalam talian (online)?

Tetapkan nombor jujukan yang meningkat kepada setiap ketibaan elemen, gunakan langkah kelupuputan dan penyingkiran belakang yang sama, dan pancarkan nilai hadapan selepas elemen ke-k dan pada setiap ketibaan terkemudian. Simpan paling banyak k indeks dan nilai calon, supaya memori tidak bergantung pada jumlah panjang strim. Ketibaan tidak mengikut urutan juga memerlukan tetingkap masa acara (event-time window), watermark, dan dasar data lewat; itu di luar model tatasusunan terisih bagi masalah ini.

Susulan 7: Bagaimanakah corak ini diperluaskan kepada pengaturcaraan dinamik berbatas (bounded dynamic programming)?

Untuk pengulangan di mana keadaan semasa bersamaan dengan kosnya sendiri ditambah maksimum daripada k keadaan sebelumnya, simpan deque yang diisih mengikut nilai DP. Bahagian hadapan membekalkan maksimum peralihan, manakala kelupuputan masih bergantung pada indeks. Sasaran perbandingan berubah daripada nums[i] kepada dp[i], tetapi pembuktiannya masih bergantung pada keadaan yang lebih baharu dan tidak lebih kecil yang mendominasi keadaan yang lebih lama.