Beauté maximale d'un tableau après l'application de l'opération

2779. Beauté maximale d'un tableau après l'opération d'application

Difficulté :Moyen

Sujets : Tableau, recherche binaire, fenêtre coulissante, tri

Vous recevez un tableau indexé à 0 et un non négatif entier k.

En une seule opération, vous pouvez effectuer les opérations suivantes :

• Choisissez un index i qui n'a pas été choisi auparavant dans la plage [0, nums.length - 1].
• Remplacez nums[i] par n'importe quel entier de la plage [nums[i] - k, nums[i] k].

La beauté du tableau est la longueur de la sous-séquence la plus longue composée d'éléments égaux.

Renvoyer la beauté maximale possible des numéros du tableau après avoir appliqué l'opération un certain nombre de fois.

Notez que vous ne pouvez appliquer l'opération à chaque index qu'une seule fois.

Une sous-séquence d'un tableau est un nouveau tableau généré à partir du tableau d'origine en supprimant certains éléments (éventuellement aucun) sans changer l'ordre des éléments restants.

Exemple 1 :

• Entrée : nums = [4,6,1,2], k = 2
• Sortie : 3
• Explication : Dans cet exemple, nous appliquons les opérations suivantes :
  • Choisissez l'index 1, remplacez-le par 4 (dans la plage [4,8]), nums = [4,4,1,2].
  • Choisissez l'index 3, remplacez-le par 4 (dans la plage [0,4]), nums = [4,4,1,4].
  • Après les opérations appliquées, la beauté du tableau nums est de 3 (sous-séquence constituée des indices 0, 1 et 3).
  • Il peut être prouvé que 3 est la longueur maximale possible que nous pouvons atteindre.

Exemple 2 :

• Entrée : nums = [1,1,1,1], k = 10
• Sortie : 4
• Explication : Dans cet exemple, nous n'avons à appliquer aucune opération.
  • La beauté des nombres du tableau est 4 (tableau entier).

Contraintes :

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

Indice :

1. Trier le tableau.
2. Le problème devient le suivant : trouver le sous-tableau maximum A[i … j] tel que A[j] - A[i] ≤ 2 * k.

Solution :

Nous pouvons utiliser le tri et une approche par fenêtre coulissante.

Approche:

1. Trier le tableau : Le tri simplifie l'identification des sous-séquences où la différence entre le plus grand et le plus petit élément ne dépasse pas 2k.
2. Technique de fenêtre coulissante : Maintenir une fenêtre d'indices [i, j] où la différence nums[j] - nums[i] <= 2k. Ajustez i ou j pour maximiser la taille de la fenêtre.

Implémentons cette solution en PHP : 2779. Beauté maximale d'un tableau après l'opération d'application

<?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>
  
  
  Explication:
</h3>

<ol>
<li>
<strong>Tri du tableau</strong> :

<ul>
<li>Le tri garantit que la fenêtre définie par les indices <em><strong>[i, j]</strong></em> contient tous les éléments par ordre croissant, ce qui facilite la vérification de la différence entre les valeurs les plus petites et les plus grandes dans la fenêtre.</li>
</ul>
</li>
<li>
<strong>Fenêtre coulissante</strong> :

<ul>
<li>Commencez par i et j au début.</li>
<li>Agrandissez la fenêtre en incrémentant j et gardez la fenêtre valide en incrémentant i chaque fois que la condition <em><strong>nums[j] - nums[i] > 2k</strong></em> est violé.</li>
<li>A chaque étape, calculez la taille de la fenêtre valide actuelle <em><strong>j - i 1</strong></em> et mettez à jour le maxBeauty.</li>
</ul>
</li>
</ol>


<hr>

<h3>
  
  
  Analyse de complexité :
</h3>

<ol>
<li>
<strong>Complexité temporelle</strong> :

<ul>
<li>Tri du tableau : <em><strong>O(n log n)</strong></em>.</li>
<li>Parcours de la fenêtre coulissante : <em><strong>O(n)</strong></em>.</li>
<li>Global : <em><strong>O(n log n)</strong></em>.</li>
</ul>
</li>
<li>
<strong>Complexité spatiale</strong> :

<ul>
<li>
<em><strong>O(1)</strong></em>, car la solution n'utilise que quelques variables supplémentaires.</li>
</ul>
</li>
</ol>


<hr>

<h3>
  
  
  Exemples :
</h3>

<h4>
  
  
  Entrée 1 :
</h4>



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

Entrée 2 :

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

Cette solution respecte les contraintes et calcule efficacement le résultat pour les entrées volumineuses.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!