Le plus grand rectangle de l'histogramme

Présentation du problème

La tâche consiste à trouver la plus grande zone de rectangle pouvant être formée dans un histogramme. Chaque barre de l'histogramme a une largeur de 1 et la hauteur de chaque barre est donnée par un tableau d'entiers non négatifs.

Par exemple, étant donné le tableau des hauteurs [2, 1, 5, 6, 2, 3], la plus grande zone de rectangle dans l'histogramme est 10.

Approche de solution

Le problème peut être résolu efficacement en utilisant une approche basée sur la pile. Cette approche implique de maintenir une pile pour garder une trace des indices des barres de l'histogramme, nous permettant de calculer la surface maximale du rectangle en temps linéaire. Voici une description détaillée de l'algorithme :

1. Initialiser les variables

• len : La longueur du tableau des hauteurs.
• pile : Une pile vide utilisée pour stocker les indices des barres d'histogramme.
• max : Une variable pour garder une trace de la surface maximale du rectangle trouvée jusqu'à présent.
• h : La hauteur de la barre qui est extraite de la pile.
• w : La largeur du rectangle formé de hauteur h.

2. Parcourir le tableau de hauteurs

Nous parcourons le tableau des hauteurs de gauche à droite et ajoutons également une barre virtuelle finale de hauteur 0 à la fin du tableau pour nous assurer que toutes les barres sont traitées.

Étapes de l'itération :

• Pousser l'index de la barre actuelle : Pour chaque barre, poussez son index sur la pile. Cependant, avant de faire cela, nous devons nous assurer que la barre actuelle est plus haute que la barre de l'index stocké en haut de la pile. Si ce n'est pas le cas, nous extrayons les barres de la pile pour calculer l'aire des rectangles qui peuvent être formés en utilisant la barre à l'index éclaté comme la plus petite barre (c'est-à-dire la hauteur du rectangle).

• Pop de la pile et calcul de la zone :

  • Supprimez l'index supérieur de la pile. Cet indice représente la hauteur de la plus petite barre du rectangle.
  • Calculez la largeur du rectangle. Si la pile est vide après l'éclatement, cela signifie que la barre éclatée était la plus petite jusqu'à présent et que sa largeur s'étend du début du tableau jusqu'à l'index actuel. Sinon, la largeur est déterminée par la distance entre l'index actuel et l'index maintenant en haut de la pile, moins un.
  • Calculez l'aire du rectangle en utilisant la hauteur et la largeur et mettez à jour la variable max si cette zone est plus grande.

3. Gérer les barres restantes dans la pile

Après avoir parcouru toutes les barres, il se peut qu'il reste encore quelques barres dans la pile. Ces barres auraient des hauteurs qui n'ont pas été traitées car il n'y avait pas de barre plus courte à droite. Nous devons traiter ces barres restantes de la même manière en les retirant de la pile et en calculant la surface.

Explication détaillée du code

Voici le code JavaScript avec des commentaires expliquant chaque partie :

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
  var len = heights.length;
  var stack = [];
  var max = 0;
  var h = 0;
  var w = 0;

  // Iterate through the heights array
  for (var i = 0; i <= len; i++) {
    // Ensure the loop processes the virtual bar with height 0 at the end
    while (stack.length && (i === len || heights[i] <= heights[stack[stack.length - 1]])) {
      // Pop the top index from the stack
      h = heights[stack.pop()];
      // Calculate the width of the rectangle
      w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      // Update the maximum area found so far
      max = Math.max(max, h * w);
    }
    // Push the current index onto the stack
    stack.push(i);
  }

  return max;
};

Analyse de complexité

• Complexité temporelle : O(n), où n est le nombre de barres dans l'histogramme. Chaque barre est poussée et retirée de la pile au plus une fois.
• Complexité spatiale : O(n) pour la pile utilisée pour suivre les indices.

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!