Cari Kuasa Subarray Saiz K I

3254. Cari Kuasa K-Size Subarrays I

Kesukaran: Sederhana

Topik: Tatasusunan, Tingkap Gelongsor

Anda diberi tatasusunan nombor bulat panjang n dan positif integer k.

kuasa tatasusunan ditakrifkan sebagai:

• Elemen maksimum jika semua elemennya berturut-turut dan diisih dalam urutan menaik.
• -1 jika tidak.

Anda perlu mencari kuasa semua sub-baris¹ nombor saiz k.

Kembalikan hasil tatasusunan integer bersaiz n - k 1, dengan hasil[i] ialah kuasa nombor[i..(i k - 1)].

Contoh 1:

• Input: nombor = [1,2,3,4,3,2,5], k = 3
• Output: [3,4,-1,-1,-1]
• Penjelasan: Terdapat 5 subarray nombor saiz 3:
  • [1, 2, 3] dengan elemen maksimum 3.
  • [2, 3, 4] dengan unsur maksimum 4.
  • [3, 4, 3] yang elemennya bukan berturut-turut.
  • [4, 3, 2] yang elemennya tidak diisih.
  • [3, 2, 5] yang elemennya bukan berturut-turut.

Contoh 2:

• Input: nombor = [2,2,2,2,2], k = 4
• Output: [-1,-1]

Contoh 3:

• Input: nombor = [3,2,3,2,3,2], k = 2
• Output: [-1,3,-1,3,-1]

Kekangan:

• 1 <= n == nums.length <= 500
• 1 <= nums[i] <= 10⁵
• 1 <= k <= n

Petunjuk:

1. Bolehkah kita menggunakan penyelesaian kekerasan dengan gelung bersarang dan HashSet?

Penyelesaian:

Kami boleh memecahkan tugas seperti berikut:

Pecahan Masalah:

1. Kami diberi nombor tatasusunan panjang n, dan integer positif k. Kita perlu mempertimbangkan semua subarray saiz k dan mengira kuasanya.
2. kuasa subbaris ialah:
   • Elemen maksimum subarray jika semua elemen berturut-turut dan diisih dalam urutan menaik.
   • -1 jika tidak.
3. Kita perlu mengembalikan tatasusunan saiz n - k 1, di mana setiap elemen sepadan dengan kuasa subbaris masing-masing.

Pelan:

1. Pendekatan Tetingkap Gelongsor: Kami akan meluncur ke atas tatasusunan dan menyemak setiap subarray panjang k.
2. Semak sama ada Subarray Diisih: Kita perlu menyemak sama ada subarray mempunyai elemen yang berturutan dan diisih dalam tertib menaik.
3. Kembali Maksimum atau -1: Jika subarray sah, kami mengembalikan elemen maksimum. Jika tidak, kembalikan -1.

Langkah-langkah:

1. Periksa sama ada subarray diisih:
   • Subarray yang diisih dengan elemen berturut-turut harus mempunyai sifat: nums[i 1] - nums[i] == 1 untuk setiap i dalam subarray.
2. Tetingkap Gelongsor:
   • Untuk setiap subbaris panjang k, semak sama ada ia diisih dan kembalikan elemen maksimum jika sah, jika tidak, kembalikan -1.

Mari laksanakan penyelesaian ini dalam PHP: 3254. Cari Kuasa K-Size Subarrays I

  
  
  Penjelasan:




Tetingkap Gelongsor: Kami menggunakan gelung for daripada i = 0 hingga i = n - k untuk mempertimbangkan semua subarray saiz k. Untuk setiap subarray, kami menggunakan array_slice() untuk mengekstrak subarray.

Semakan Isih: Untuk setiap subarray, kami menyemak sama ada ia diisih dengan unsur berturutan dengan mengulang subarray dan menyemak sama ada setiap pasangan unsur berturutan mempunyai perbezaan 1.

Keputusan: Jika subarray adalah sah, kami menambahkan nilai maksimum subarray pada hasil. Jika tidak, kami tambahkan -1.



  
  
  Kerumitan Masa:



Kami mengulangi n - k 1 subbarray.
Untuk setiap sub-baris, kami menyemak sama ada elemen adalah berturut-turut, yang mengambil masa O(k).
Oleh itu, kerumitan masa keseluruhan ialah O((n - k 1) * k) yang memudahkan kepada O(n * k).



  
  
  Pertimbangan Kes Edge:



Jika k = 1, setiap subbaris diisih secara remeh (ia hanya mengandungi satu elemen), dan kuasa setiap subbaris akan menjadi elemen itu sendiri.
Jika subarray tidak berturut-turut, ia akan segera kembali -1.



  
  
  Contoh Output:



Untuk nombor = [1, 2, 3, 4, 3, 2, 5], k = 3, output ialah [3, 4, -1, -1, -1].
Untuk nombor = [2, 2, 2, 2, 2], k = 4, output ialah [-1, -1].
Untuk nombor = [3, 2, 3, 2, 3, 2], k = 2, output ialah [-1, 3, -1, 3, -1].


Penyelesaian ini harus berkesan untuk kekangan masalah.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub








Subarray: Subarray ialah jujukan unsur tidak kosong bersebelahan dalam tatasusunan. ↩





          

            
  

            
        
Atas ialah kandungan terperinci Cari Kuasa Subarray Saiz K I. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!