Kontinuierliche Subarrays

2762. Kontinuierliche Subarrays

Schwierigkeit:Mittel

Themen: Schiebefenster, Array, geordnete Menge, Heap (Prioritätswarteschlange), Warteschlange, monotone Warteschlange, zwei Zeiger, geordnete Karte, Hash-Tabelle, dynamische Programmierung, Zählen, Mathematik, binärer Suchbaum, Segmentbaum, Baum, Stapel, binäre Suche, monotoner Stapel, Memoisierung, Iterator, Greedy, Tiefensuche, Rekursion

Sie erhalten ein 0-indiziertes ganzzahliges Array mit Zahlen. Ein Subarray von Nums heißt kontinuierlich, wenn:

• Seien i, i 1, ..., j die Indizes im Subarray. Dann gilt für jedes Indexpaar i <= i₁, i₂ <= j, 0 <= |nums[i₁] - nums[i₂]| <= 2.

Gibt die Gesamtzahl der kontinuierlichen Subarrays zurück.

Ein Subarray ist eine zusammenhängende nicht leere Folge von Elementen innerhalb eines Arrays.

Beispiel 1:

• Eingabe: nums = [5,4,2,4]
• Ausgabe: 8
• Erklärung:
  • Kontinuierliches Unterarray der Größe 1: [5], [4], [2], [4].
  • Kontinuierliches Subarray der Größe 2: [5,4], [4,2], [2,4].
  • Kontinuierliches Subarray der Größe 3: [4,2,4].
  • Es gibt keine Unterarrys der Größe 4.
  • Gesamtzahl kontinuierlicher Subarrays = 4 3 1 = 8.
  • Es kann gezeigt werden, dass es keine kontinuierlichen Subarrays mehr gibt.

Beispiel 2:

• Eingabe: nums = [1,2,3]
• Ausgabe: 6
• Erklärung:
  • Kontinuierliches Unterarray der Größe 1: [1], [2], [3].
  • Kontinuierliches Subarray der Größe 2: [1,2], [2,3].
  • Kontinuierliches Subarray der Größe 3: [1,2,3].
  • Gesamtzahl kontinuierlicher Subarrays = 3 2 1 = 6.

Einschränkungen:

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

Hinweis:

1. Versuchen Sie es mit der Schiebefenstertechnik.
2. Verwenden Sie einen Satz oder eine Karte, um das Maximum und Minimum von Subarrays zu verfolgen.

Lösung:

Wir können die Schiebefenstertechnik verwenden, um die Anzahl kontinuierlicher Subarrays effizient zu berechnen. Wir behalten ein gültiges Fenster bei, in dem die Differenz zwischen den Maximal- und Minimalwerten im Subarray höchstens 2 beträgt. Um die Maximal- und Minimalwerte innerhalb des aktuellen Fensters effizient zu verfolgen, können wir zwei Deques (eine) verwenden für das Maximum und eine für das Minimum).

Ansatz

1. Verwenden Sie die Schiebefenstertechnik mit zwei Zeigern: links und rechts.
2. Verwenden Sie zwei Deques:
   • Eine, um Indizes von Elementen in absteigender Reihenfolge für den Maximalwert zu verfolgen.
   • Eine, um Indizes von Elementen in aufsteigender Reihenfolge für den Mindestwert zu verfolgen.
3. Für jedes Indexrecht:
   • Aktualisieren Sie die Deques, um das aktuelle Fenster widerzuspiegeln.
   • Stellen Sie sicher, dass das Fenster gültig bleibt (Differenz zwischen Maximum und Minimum ≤ 2). Wenn ungültig, erhöhen Sie den linken Zeiger, um das Fenster zu verkleinern.
   • Zählen Sie die Anzahl der gültigen Subarrays, die am Index rechts enden, als (rechts – links 1).
4. Gibt die Gesamtzahl der Subarrays zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 2762. Kontinuierliche Subarrays

<?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>
  
  
  Erläuterung:
</h3>

<ol>
<li><p><strong>Schiebefenster:</strong><br><br>
Der linke Zeiger bewegt sich nur dann vorwärts, wenn das Fenster ungültig wird (d. h. wenn die Differenz zwischen dem Maximal- und Minimalwert 2 überschreitet). Der rechte Zeiger erweitert das Fenster, indem er das Array durchläuft.</p></li>
<li>
<p><strong>Deques für Maximum und Minimum:</strong></p>

<ul>
<li>Die maxDeque enthält immer Indizes von Elementen in absteigender Reihenfolge und stellt sicher, dass der Maximalwert im aktuellen Fenster vorne liegt (maxDeque[0]).</li>
<li>Die minDeque enthält immer Indizes von Elementen in aufsteigender Reihenfolge und stellt sicher, dass der Mindestwert im aktuellen Fenster vorne liegt (minDeque[0]).</li>
</ul>
</li>
<li><p><strong>Subarrays zählen:</strong><br><br>
Für jedes Rechts ist die Anzahl der gültigen Subarrays, die rechts enden, gleich (rechts – links 1), da alle Subarrays von links nach rechts gültig sind.</p></li>
<li><p><strong>Effizienz:</strong><br><br>
Jedes Element wird höchstens einmal zu den Deques hinzugefügt und daraus entfernt, wodurch die Zeitkomplexität <strong>O(n)</strong> wird. Die Raumkomplexität ist aufgrund der Deques <strong>O(n)</strong>.</p></li>
</ol>


<hr>

<h3>
  
  
  Ausgabe
</h3>



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

Komplexitätsanalyse

1. Zeitkomplexität:

   • Jedes Element wird höchstens einmal aus den Deques verschoben und entfernt.
   • Die Gesamtzeitkomplexität beträgt O(n).

2. Weltraumkomplexität:

   • Deques speichern Indizes mit einer maximalen Größe von n.
   • Die Raumkomplexität beträgt O(n).

Diese Implementierung ist effizient und funktioniert innerhalb der bereitgestellten Einschränkungen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonKontinuierliche Subarrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!