Maximale Schönheit eines Arrays nach der Operation

2779. Maximale Schönheit eines Arrays nach der Operation

Schwierigkeit:Mittel

Themen:Array, Binäre Suche, Schiebefenster, Sortieren

Sie erhalten eine 0-indizierte Array-Nummer und eine nicht negative ganze Zahl k.

In einem Arbeitsgang können Sie Folgendes tun:

• Wählen Sie einen Index i, der noch nicht ausgewählt wurde aus dem Bereich [0, nums.length - 1].
• Ersetzen Sie nums[i] durch eine beliebige ganze Zahl aus dem Bereich [nums[i] - k, nums[i] k].

Die Schönheit des Arrays ist die Länge der längsten Teilsequenz, die aus gleichen Elementen besteht.

Gibt die maximale mögliche Schönheit der Array-Nummern zurück, nachdem die Operation beliebig oft angewendet wurde.

Beachten Sie, dass Sie den Vorgang nur einmal auf jeden Index anwenden können.

Eine Teilsequenz eines Arrays ist ein neues Array, das aus dem ursprünglichen Array generiert wird, indem einige Elemente (möglicherweise keines) gelöscht werden, ohne die Reihenfolge der verbleibenden Elemente zu ändern.

Beispiel 1:

• Eingabe: nums = [4,6,1,2], k = 2
• Ausgabe: 3
• Erklärung: In diesem Beispiel wenden wir die folgenden Operationen an:
  • Wählen Sie Index 1 und ersetzen Sie ihn durch 4 (aus dem Bereich [4,8]), Nums = [4,4,1,2].
  • Wählen Sie Index 3, ersetzen Sie ihn durch 4 (aus dem Bereich [0,4]), Nums = [4,4,1,4].
  • Nach den angewendeten Operationen beträgt die Schönheit der Array-Nummern 3 (Teilfolge bestehend aus den Indizes 0, 1 und 3).
  • Es kann bewiesen werden, dass 3 die maximal mögliche Länge ist, die wir erreichen können.

Beispiel 2:

• Eingabe: nums = [1,1,1,1], k = 10
• Ausgabe: 4
• Erklärung: In diesem Beispiel müssen wir keine Operationen anwenden.
  • Das Schöne an den Array-Nummern ist 4 (gesamtes Array).

Einschränkungen:

• 1 <= nums.length <= 10⁵
• 0 <= nums[i], k <= 10⁵

Hinweis:

1. Sortieren Sie das Array.
2. Das Problem wird wie folgt: Finden Sie das maximale Subarray A[i … j], so dass A[j] - A[i] ≤ 2 * k.

Lösung:

Wir können Sortierung und einen Schiebefenster-Ansatz nutzen.

Ansatz:

1. Array sortieren: Das Sortieren vereinfacht die Identifizierung von Teilsequenzen, bei denen die Differenz zwischen dem größten und kleinsten Element 2k nicht überschreitet.
2. Schiebefenstertechnik: Pflegen Sie ein Fenster mit Indizes [i, j] wobei die Differenz nums[j] - nums[i] <= 2k. Passen Sie i oder j an, um die Fenstergröße zu maximieren.

Lassen Sie uns diese Lösung in PHP implementieren: 2779. Maximale Schönheit eines Arrays nach der Operation

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

// Example Usage:
$nums1 = [4, 6, 1, 2];
$k1 = 2;
echo maximumBeauty($nums1, $k1) . "\n"; // Output: 3

$nums2 = [1, 1, 1, 1];
$k2 = 10;
echo maximumBeauty($nums2, $k2) . "\n"; // Output: 4
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<strong>Sortieren des Arrays</strong>:

<ul>
<li>Sortieren stellt sicher, dass das durch die Indizes <em><strong>[i, j]</strong></em> definierte Fenster alle Elemente in aufsteigender Reihenfolge enthält, was es einfacher macht, den Unterschied zwischen dem kleinsten und dem größten Wert zu überprüfen das Fenster.</li>
</ul>
</li>
<li>
<strong>Schiebefenster</strong>:

<ul>
<li>Beginnen Sie mit i und j am Anfang.</li>
<li>Erweitern Sie das Fenster, indem Sie j erhöhen, und halten Sie das Fenster gültig, indem Sie i erhöhen, wann immer die Bedingung <em><strong>nums[j] - nums[i] > 2k</strong></em> wird verletzt.</li>
<li>Berechnen Sie bei jedem Schritt die Größe des aktuell gültigen Fensters <em><strong>j - i 1</strong></em> und aktualisieren Sie maxBeauty.</li>
</ul>
</li>
</ol>


<hr>

<h3>
  
  
  Komplexitätsanalyse:
</h3>

<ol>
<li>
<strong>Zeitkomplexität</strong>:

<ul>
<li>Sortieren des Arrays: <em><strong>O(n log n)</strong></em>.</li>
<li>Durchquerung des Schiebefensters: <em><strong>O(n)</strong></em>.</li>
<li>Insgesamt: <em><strong>O(n log n)</strong></em>.</li>
</ul>
</li>
<li>
<strong>Weltraumkomplexität</strong>:

<ul>
<li>
<em><strong>O(1)</strong></em>, da die Lösung nur wenige zusätzliche Variablen verwendet.</li>
</ul>
</li>
</ol>


<hr>

<h3>
  
  
  Beispiele:
</h3>

<h4>
  
  
  Eingabe 1:
</h4>



<pre class="brush:php;toolbar:false">$nums = [4, 6, 1, 2];
$k = 2;
echo maximumBeauty($nums, $k); // Output: 3

Eingabe 2:

$nums = [1, 1, 1, 1];
$k = 10;
echo maximumBeauty($nums, $k); // Output: 4

Diese Lösung hält sich an die Einschränkungen und berechnet das Ergebnis für große Eingaben effizient.

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 vonMaximale Schönheit eines Arrays nach der Operation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!