Subarray Berterusan

2762. Subarray Berterusan

Kesukaran: Sederhana

Topik: Tetingkap Gelongsor, Tatasusunan, Set Tersusun, Timbunan (Baris Gilir Keutamaan), Baris Gilir, Baris Monotonik, Dua Penunjuk, Peta Tertib, Jadual Cincang, Pengaturcaraan Dinamik, Pengiraan, Matematik, Pokok Carian Binari, Pokok Segmen, Pokok, Timbunan, Carian Perduaan, Timbunan Monotonic, Memoisasi, Lelaran, Tamak, Carian Pertama Kedalaman, Rekursi

Anda diberi 0-diindeks nombor tatasusunan integer. Subarray nombor dipanggil berterusan jika:

• Biar i, i 1, ..., j menjadi indeks dalam subbaris. Kemudian, untuk setiap pasangan indeks i <= i₁, i₂ <= j, 0 <= |nums[i₁] - nombor[i₂]| <= 2.

Pulangan jumlah bilangan berterusan sub-baris.

Subarray ialah jujukan tidak kosong yang bersebelahan bagi unsur dalam tatasusunan.

Contoh 1:

• Input: nombor = [5,4,2,4]
• Output: 8
• Penjelasan:
  • Subarray berterusan saiz 1: [5], [4], [2], [4].
  • Subarray berterusan saiz 2: [5,4], [4,2], [2,4].
  • Subarray berterusan saiz 3: [4,2,4].
  • Tiada subarry bersaiz 4.
  • Jumlah subarray berterusan = 4 3 1 = 8.
  • Ia boleh ditunjukkan bahawa tiada lagi subarray berterusan.

Contoh 2:

• Input: nombor = [1,2,3]
• Output: 6
• Penjelasan:
  • Subarray berterusan saiz 1: [1], [2], [3].
  • Subarray berterusan saiz 2: [1,2], [2,3].
  • Subarray berterusan saiz 3: [1,2,3].
  • Jumlah subarray berterusan = 3 2 1 = 6.

Kekangan:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁹

Petunjuk:

1. Cuba gunakan teknik tingkap gelongsor.
2. Gunakan set atau peta untuk menjejaki maksimum dan minimum subarray.

Penyelesaian:

Kita boleh menggunakan teknik tetingkap gelongsor untuk mengira bilangan subarray berterusan dengan cekap. Kami akan mengekalkan tetingkap yang sah di mana perbezaan antara nilai maksimum dan minimum dalam subarray adalah paling banyak 2. Untuk menjejaki nilai maksimum dan minimum dalam tetingkap semasa dengan cekap, kami boleh menggunakan dua deques (satu untuk maksimum dan satu untuk minimum).

Pendekatan

1. Gunakan teknik tetingkap gelongsor dengan dua penunjuk: kiri dan kanan.
2. Gunakan dua deques:
   • Satu untuk menjejak indeks unsur dalam tertib menurun untuk nilai maksimum.
   • Satu untuk menjejak indeks unsur dalam tertib menaik untuk nilai minimum.
3. Untuk setiap indeks kanan:
   • Kemas kini deques untuk mencerminkan tetingkap semasa.
   • Pastikan tetingkap kekal sah (perbezaan antara maksimum dan minimum ≤ 2). Jika tidak sah, naikkan penunjuk kiri untuk mengecilkan tetingkap.
   • Kira bilangan subarray yang sah berakhir pada indeks kanan sebagai (kanan - kiri 1).
4. Kembalikan jumlah kiraan subarray.

Mari laksanakan penyelesaian ini dalam PHP: 2762. Subarray Berterusan

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function continuousSubarrays($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [5, 4, 2, 4];
echo continuousSubarrays($nums1) . "\n"; // Output: 8

$nums2 = [1, 2, 3];
echo continuousSubarrays($nums2) . "\n"; // Output: 6
?>




<h3>
  
  
  Penjelasan:
</h3>

<ol>
<li><p><strong>Tetingkap Gelongsor:</strong><br><br>
Penunjuk kiri bergerak ke hadapan hanya apabila tetingkap menjadi tidak sah (iaitu, perbezaan antara nilai maksimum dan minimum melebihi 2). Penunjuk kanan mengembangkan tetingkap dengan mengulangi tatasusunan.</p></li>
<li>
<p><strong>Deques untuk Maksimum dan Minimum:</strong></p>

<ul>
<li>MaxDeque sentiasa menyimpan indeks elemen dalam tertib menurun, memastikan nilai maksimum dalam tetingkap semasa berada di hadapan (maxDeque[0]).</li>
<li>MinDeque sentiasa menyimpan indeks unsur dalam tertib menaik, memastikan nilai minimum dalam tetingkap semasa berada di hadapan (minDeque[0]).</li>
</ul>
</li>
<li><p><strong>Mengira Subarray:</strong><br><br>
Untuk setiap kanan, bilangan subarray yang sah berakhir di sebelah kanan adalah sama dengan (kanan - kiri 1), kerana semua subarray dari kiri ke kanan adalah sah.</p></li>
<li><p><strong>Kecekapan:</strong><br><br>
Setiap elemen ditambah dan dialih keluar daripada deque paling banyak sekali, menjadikan kerumitan masa <strong>O(n)</strong>. Kerumitan ruang ialah <strong>O(n)</strong> disebabkan oleh deques.</p></li>
</ol>


<hr>

<h3>
  
  
  Keluaran
</h3>



<pre class="brush:php;toolbar:false">8
6

---

Analisis Kerumitan

1. Kerumitan Masa:

   • Setiap elemen ditolak dan muncul dari deque paling banyak sekali.
   • Jumlah kerumitan masa ialah O(n).

2. Kerumitan Angkasa:

   • Deques menyimpan indeks, dengan saiz maksimum n.
   • Kerumitan ruang ialah O(n).

Pelaksanaan ini cekap dan berfungsi dalam kekangan yang disediakan.

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

Atas ialah kandungan terperinci Subarray Berterusan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!