Posting ini ditujukan untuk orang-orang yang memecahkan masalah jendela geser selama perjalanan LeetCode mereka.

  1. Mengenali permasalahan jendela geser
  2. Pendekatan metodologis untuk memecahkan masalah jendela geser
  3. Pendekatan untuk 239. “Jendela Geser Maksimum”
  4. Kompleksitas ruang dan waktu
  5. Kasus tepi
  6. Catatan tentang tipe struktur data linier pada input: array atau string
  7. JavaScript yang diketik dengan lembut

Mengenali masalah jendela geser

Masalah jendela geser (SWPs) adalah kategori masalah yang relatif umum yang akan Anda lihat selama wawancara. Ide utama dari masalah jendela geser adalah Anda diberikan struktur data linier, seperti string atau array, dan Anda harus mengoptimalkan beberapa batasan di sekitar jumlah minimum atau maksimum hal yang harus benar tentang kumpulan item dalam string input atau array input. Jadi, misalnya, beberapa masalah jendela geser klasik adalah “Substring Terpanjang Tanpa Karakter Berulang”, “Penggantian Karakter Berulang Terpanjang”, “Substring Jendela Minimum”, dan “Jendela Geser Maksimum”. Ide umum untuk semua masalah jendela geser adalah Anda mempertahankan jendela saat melintasi struktur data linier. Jendela adalah beberapa subkumpulan elemen di dalam kumpulan elemen yang terdapat dalam array atau string yang diteruskan sebagai parameter.

Kami mengenali masalah ini sebagai masalah jendela geser karena 1, pertanyaannya secara harfiah disebut “Jendela Geser Maksimum,” dan 2, ada beberapa invarian yang harus dipertahankan sambil melacak beberapa bagian data dalam pertanyaan meminta kami untuk kembali. Mengenali pertanyaan sebagai masalah jendela geser dan bukan masalah grafik, antrian prioritas, atau daftar tertaut hanya dapat membantu dalam memahami pertanyaan sepenuhnya.

Pendekatan metodologis untuk memecahkan masalah jendela geser

Ada pertanyaan dasar yang ingin Anda jawab secara sederhana sebelum menerapkan dan menulis kode Anda. Pertanyaan-pertanyaan ini berlaku untuk setiapSWP.

  1. Apakah pertanyaannya meminta saya untuk menerapkan jendela geser berukuran tetap atau jendela geser berukuran dinamis?
  2. Dalam kondisi apa penunjuk kanan bergerak?
  3. Kapan fungsi tersebut akan membaca solusi sementara?
  4. Bagaimana fungsi tersebut menentukan solusi optimal?
  5. Dalam kondisi apa penunjuk kiri bergerak?
  6. Kategori manakah yang termasuk dalam SWP?

Selanjutnya kita bisa memikirkan bentuk masalah jendela geser. Karena permasalahan jendela geser selalu diselesaikan untuk beberapa subset maksimum atau minimum dari array input atau string input, hanya ada begitu banyak cara untuk menampilkan masalah jendela geser.

  1. Cepat/lambat: Penunjuk kanan bergerak lebih cepat daripada penunjuk kiri. Pertanyaan yang dicakup oleh postingan ini di LeetCode 239: “Substring Jendela Maksimum” adalah SWP yang cepat/lambat.
  2. Fast/catchup: Satu-satunya perbedaan antara soal cepat/lambat dan soal cepat/catchup adalah soal cepat/catchup memiliki penunjuk kiri yang “melompat” ke lokasi penunjuk kanan. LeetCode 53. “Max Subarray” adalah contohnya. Lompatan terjadi secara kondisional pada beberapa peristiwa yang terjadi seperti CurrentSumInteger di “Max Subarray” menjadi negatif.
  3. Cepat/tertinggal: Saat melakukan perulangan pada array, fungsinya mempertahankan invarian di mana solusi hanya dapat diubah oleh elemen yang berjarak beberapa titik dari nilai array saat ini. Lihat masalah "" Perampok Rumah "".
  4. Depan/belakang: Penunjuk kiri diinisialisasi pada indeks ke-0 sedangkan penunjuk lainnya diinisialisasi pada indeks terakhir. Lihat “Menjebak Air Hujan.”

Karena setiap masalah jendela geser harus termasuk dalam salah satu dari empat kategori ini, kita dapat bertanya “kategori manakah yang termasuk dalam SWP saat ini?” Kami tahu jawabannya akan selalu berupa salah satu dari empat pilihan ini: Cepat/lambat, cepat/kejar, cepat/tertinggal, dan depan/belakang.

Pendekatan untuk “Jendela Geser Maksimum”

  1. Apakah pertanyaannya meminta saya untuk menggeser jendela berukuran tetap atau jendela berukuran dinamis?
  • Jendela berukuran tetap dengan panjang k.

2. Dalam kondisi apa penunjuk kanan bergerak?

  • Penunjuk kanan bergerak selama indeks penunjuk kanan kurang dari panjang larik masukan.

3. Kapan fungsi tersebut membaca solusi sementara?

  • Fungsi ini membaca solusi sementara setiap kali indeks penunjuk kanan berubah. Solusi sementara dalam “Sliding Window Maximum” yang harus dilacak adalah nilai maksimum yang telah diamati.

4. Bagaimana fungsi tersebut menentukan solusi optimal?

  • Selama indeks penunjuk kanan kurang dari panjang larik masukan, dan selama ukuran jendela sama dengan k, maka berapa pun nilai maksimum saat ini yang telah diamati sejauh ini akan dimasukkan ke larik keluaran .

5. Dalam kondisi apa penunjuk kiri bergerak?

  • Penunjuk kiri bergerak ketika ukuran jendela telah mencapai k.

6. Termasuk dalam kategori manakah SWP saat ini?

  • "Jendela Geser Maksimum" adalah SWP yang cepat/lambat.
const slidingWindowMaximum = (numsArr, kInt) => {
    if (kInt > numsArr.length){
        return [];
    }
    let rightPtrInt = 0;
    let leftPtrInt = 0;
    let maxValInt = -Infinity;
    let maxValIndexInt = -1;
    let outputArr = [];
    while (rightPtrInt < numsArr.length){
        let numInt = numsArr[rightPtrInt];
        if (numInt >= maxValInt){
            maxValInt = numInt;
            maxValIndexInt = rightPtrInt;
        }
        rightPtrInt++;
        if (rightPtrInt - leftPtrInt === kInt){
            outputArr.push(maxValInt);
            // handle the case where the maxVal leaves when leftPtrInt is about to moves
            if (maxValIndexInt === leftPtrInt){
                maxValInt = -Infinity;
                // perform O(kInt) scan to find and store the maximum value in the window
                for (let xInt = leftPtrInt+1; xInt < rightPtrInt; xInt++){
                    let numInt = numsArr[xInt];
                    if (numInt >= maxValInt){
                        maxValInt = numInt;
                        maxValIndexInt = xInt;
                    }
                }
            }
            leftPtrInt++;
        }
    }
    return outputArr;
}

/* Tests */
let nums1Arr = [1,3,-1,-3,5,3,6,7];
let k1Int = 3;

let nums2Arr = [1];
let k2Int = 1;

let nums3Arr = [1, -1];
let k3Int = 1;

let nums4Arr = [1,3,1,2,0,5];
let k4Int = 3;


console.log(slidingWindowMaximum(nums1Arr, k1Int)); // Expect [3,3,5,5,6,7]
console.log(slidingWindowMaximum(nums2Arr, k2Int)); // Expect [1]
console.log(slidingWindowMaximum(nums3Arr, k3Int)); // Expect [1, -1] 
console.log(slidingWindowMaximum(nums4Arr, k4Int)); // Expect [3,3,2,5]

Kompleksitas waktu & ruang

Metode yang saya bagikan di sini memiliki run-time O(k*(N-k)). Jendelanya berukuran k. Fungsi tersebut harus memindai jendela sebanyak N-k kali untuk menemukan nilai maksimum array.

“Tunggu,” Anda berkata, “Saya pikir masalah jendela geser dapat diimplementasikan secara efisien dengan kompleksitas waktu O(N).” Anda benar. Ada alasan untuk mengimplementasikan O(k*(N-k)) terlebih dahulu. Masalah LeetCode ini secara teknis diklasifikasikan sebagai masalah “sulit”. Meskipun solusi yang disajikan di sini bukanlah solusi yang paling efisien, menuliskan solusi ini akan membantu kita mengembangkan intuisi untuk memecahkan setiap masalah jendela geser di masa depan. Saya memilih untuk menulis tentang masalah ini karena ada pengertian yang sangat sederhana dan lugas tentang apa itu jendela geser. Seperti soal jendela geser lainnya, sebagian masalahnya terdiri dari membangun jendela, dan sebagian lagi terdiri dari melakukan sesuatu dengan elemen di dalam jendela, dan kemudian ada gagasan langsung menggeser jendela ke atas masukan. Selain itu, terlepas dari manfaatnya, dengan pengujian LeetCode saat ditulis, solusi O(k*(N — k)) akan lulus. Apakah Anda punya saran tentang cara mengimplementasikan fungsi yang lebih efisien dalam hal kompleksitas waktu? Tinggalkan pemikiran Anda di bagian komentar di bawah.

Kompleksitas ruang dari fungsi tersebut adalah O(N-k+1). Array keluaran menggunakan ruang O(N), tetapi karena ukuran jendela panjangnya k, kompleksitas ruangnya sedikit lebih kecil dari N. Kompleksitas ruang sebenarnya hanya O(N-k+1). Jumlah elemen dalam larik keluaran sama dengan berapa kali jendela dapat digeser ke atas larik masukan, atau O(N-k) ditambah nilai maksimum jendela sebelum jendela mulai digeser, yaitu O(1).

Kasing tepi

Masalah "Jendela Geser Maksimum" meminta kita untuk melacak nilai maksimum di dalam jendela geser dan menyimpan nilai maksimal dalam cache saat jendela meluncur di atas larik masukan. Seberapa besar jendela yang meluncur di atas array input? Ukuran jendela bersifat tetap dan tidak dinamis. Secara khusus, terdapat elemen k di dalam jendela, dengan k hanyalah bilangan bulat yang diteruskan sebagai parameter. Kita juga tahu jika k lebih besar dari panjang array masukan, tidak ada solusi yang mungkin. Menggeser jendela dengan ukuran k=5 elemen di atas array yang berisi 3 elemen tidak mungkin dilakukan.

// Example 1
kInteger1 = 5;
array1 = [ 1, 2, 3];
// Diagram of the window before the window has moved: [ 1, 2, 3, _, _ ]
// Result: [], an empty array

Seperti yang bisa kita lihat, ketika kInteger1 lebih besar dari panjang array1 maka tidak ada jendela valid yang dapat meluncur ke atas array input.

Catatan tentang tipe struktur data linier pada input: array atau string

Saya menulis fungsi dalam JavaScript, di mana Anda dapat mengubah string menjadi array menggunakan metode .split(). Misalnya, Anda dapat mengubah str1 = “Chicago” menjadi arr1 = [ “C”, “h”, “i”, “c”, “a”, “g”, “o”] dengan menugaskan let arr1 = str1 .membelah(""). Anda juga dapat mengubah array menjadi string menggunakan metode .join(). Mengembalikan arr1.join(“”) akan mengembalikan “Chicago.” Intinya begini: jangan biarkan struktur data linier tertentu terlalu mengkhawatirkan Anda. Jika Anda benar-benar ingin mengonversi string menjadi array karena Anda lebih menyukai metode yang terkait dengan array, opsi tersebut sepenuhnya tersedia untuk Anda. Anda sebenarnya mungkin tertarik menggunakan array daripada string karena array memiliki lebih banyak metode yang tersedia di JavaScript. Array juga mempunyai metode yang memungkinkan array diimplementasikan sebagai antrian, tumpukan, atau antrian berujung ganda (deque).

Biasanya Anda akan kesulitan menemukan solusi jendela bergerak yang lebih cepat daripada waktu O(N), yang juga dikenal sebagai waktu linier, ketika menganalisis kompleksitas waktu dari fungsi jendela geser yang berhasil. Karena runtime solusi optimal tidak lebih efisien daripada O(N), penerapan .split(“”) atau .join(“”) tidak akan berdampak buruk pada keseluruhan runtime solusi Anda.

JavaScript yang diketik dengan lembut

Jika Anda pernah menulis dalam JavaScript dan bahasa lain, seperti C# atau Java, Anda pasti mengetahui bahwa suatu variabel dapat dideklarasikan dalam JS tanpa menentukan tipe data variabel tersebut. Ada banyak hal yang disukai dalam menentukan tipe data variabel tertentu. Saya telah menulis variabel JavaScript dengan rumus ini: variableName + Int/Map/Set/Arr/Str/Node. Menentukan jenis variabel di akhir nama variabel terbukti memperjelas dan membantu ketika mereferensikan suatu variabel nanti. Nama variabel dengan jelas memberi tahu Anda sebagai pengembang tipe data apa yang diharapkan. Tidak perlu lagi memeriksa ulang kode Anda untuk melihat apakah suatu variabel berupa bilangan bulat, string, atau yang lainnya. Beri tahu saya pendapat Anda tentang JavaScript yang diketik dengan lembut di komentar.

Sekian untuk postingan kali ini! Saya harap Anda memiliki hari yang menyenangkan dan perjalanan yang menyenangkan sebagai seorang insinyur.