Sous-réseaux continus

2762. Sous-réseaux continus

Difficulté :Moyen

Sujets : Fenêtre coulissante, tableau, ensemble ordonné, tas (file d'attente prioritaire), file d'attente, file d'attente monotone, deux pointeurs, carte ordonnée, table de hachage, programmation dynamique, comptage, mathématiques, arbre de recherche binaire, Arbre de segments, Arbre, Pile, Recherche binaire, Pile monotone, Mémorisation, Itérateur, Gourmand, Recherche en profondeur d'abord, Récursivité

Vous recevez un tableau numérique indexé à 0. Un sous-tableau de nombres est appelé continu si :

• Soit i, i 1, ..., j les indices du sous-tableau. Ensuite, pour chaque paire d'indices i <= i₁, i₂ <= j, 0 <= |nums[i₁] - nums[i₂]| <= 2.

Renvoyer le nombre total de sous-tableaux continus.

Un sous-tableau est une séquence contiguë non vide d'éléments au sein d'un tableau.

Exemple 1 :

• Entrée : nums = [5,4,2,4]
• Sortie : 8
• Explication :
  • Sous-tableau continu de taille 1 : [5], [4], [2], [4].
  • Sous-tableau continu de taille 2 : [5,4], [4,2], [2,4].
  • Sous-tableau continu de taille 3 : [4,2,4].
  • Il n'y a pas de sous-arrys de taille 4.
  • Total des sous-tableaux continus = 4 3 1 = 8.
  • On peut montrer qu'il n'y a plus de sous-tableaux continus.

Exemple 2 :

• Entrée : nums = [1,2,3]
• Sortie : 6
• Explication :
  • Sous-tableau continu de taille 1 : [1], [2], [3].
  • Sous-tableau continu de taille 2 : [1,2], [2,3].
  • Sous-tableau continu de taille 3 : [1,2,3].
  • Total des sous-tableaux continus = 3 2 1 = 6.

Contraintes :

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

Indice :

1. Essayez d'utiliser la technique de la fenêtre coulissante.
2. Utilisez un ensemble ou une carte pour suivre le maximum et le minimum de sous-tableaux.

Solution :

Nous pouvons utiliser la technique de la fenêtre coulissante pour calculer efficacement le nombre de sous-réseaux continus. Nous conserverons une fenêtre valide où la différence entre les valeurs maximales et minimales dans le sous-tableau est d'au plus 2. Pour suivre efficacement les valeurs maximales et minimales dans la fenêtre actuelle, nous pouvons utiliser deux deques (un pour le maximum et un pour le minimum).

Approche

1. Utilisez la technique de la fenêtre coulissante avec deux pointeurs : gauche et droite.
2. Utilisez deux deques :
   • Un pour suivre les indices des éléments par ordre décroissant pour la valeur maximale.
   • Un pour suivre les indices des éléments par ordre croissant pour la valeur minimale.
3. Pour chaque droit d'index :
   • Mettez à jour les deques pour refléter la fenêtre actuelle.
   • Assurez-vous que la fenêtre reste valide (différence entre maximum et minimum ≤ 2). S'il n'est pas valide, incrémentez le pointeur gauche pour réduire la fenêtre.
   • Comptez le nombre de sous-tableaux valides se terminant à l'index droit comme (droite - gauche 1).
4. Renvoie le nombre total de sous-tableaux.

Implémentons cette solution en PHP : 2762. Sous-réseaux continus

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

<ol>
<li><p><strong>Fenêtre coulissante :</strong><br><br>
Le pointeur gauche avance uniquement lorsque la fenêtre devient invalide (c'est-à-dire que la différence entre les valeurs maximale et minimale dépasse 2). Le pointeur droit agrandit la fenêtre en parcourant le tableau.</p></li>
<li>
<p><strong>Deques pour Maximum et Minimum :</strong></p>

<ul>
<li>Le maxDeque contient toujours les indices des éléments par ordre décroissant, garantissant que la valeur maximale dans la fenêtre actuelle est au premier plan (maxDeque[0]).</li>
<li>Le minDeque contient toujours les indices des éléments par ordre croissant, garantissant que la valeur minimale dans la fenêtre actuelle est au premier plan (minDeque[0]).</li>
</ul>
</li>
<li><p><strong>Comptage des sous-tableaux :</strong><br><br>
Pour chaque droite, le nombre de sous-tableaux valides se terminant par la droite est égal à (droite - gauche 1), car tous les sous-tableaux de gauche à droite sont valides.</p></li>
<li><p><strong>Efficacité :</strong><br><br>
Chaque élément est ajouté et supprimé des deques au plus une fois, ce qui rend la complexité temporelle <strong>O(n)</strong>. La complexité spatiale est <strong>O(n)</strong> en raison des deques.</p></li>
</ol>


<hr>

<h3>
  
  
  Sortir
</h3>



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

---

Analyse de complexité

1. Complexité temporelle :

   • Chaque élément est poussé et retiré des deques au plus une fois.
   • La complexité temporelle totale est O(n).

2. Complexité spatiale :

   • Deques stocke des indices, d'une taille maximale de n.
   • La complexité spatiale est O(n).

Cette mise en œuvre est efficace et fonctionne dans les limites fournies.

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!