Größtes Rechteck im Histogramm

Problemübersicht

Die Aufgabe besteht darin, die größte Rechteckfläche zu finden, die in einem Histogramm gebildet werden kann. Jeder Balken im Histogramm hat eine Breite von 1 und die Höhe jedes Balkens wird durch ein Array nicht negativer Ganzzahlen angegeben.

Beispielsweise beträgt die größte Rechteckfläche im Histogramm bei gegebenem Höhenarray [2, 1, 5, 6, 2, 3] 10.

Lösungsansatz

Das Problem kann mithilfe eines stapelbasierten Ansatzes effizient gelöst werden. Bei diesem Ansatz wird ein Stapel verwaltet, um die Indizes der Histogrammbalken zu verfolgen, sodass wir die maximale Rechteckfläche in linearer Zeit berechnen können. Hier ist eine detaillierte Aufschlüsselung des Algorithmus:

1. Variablen initialisieren

• len: Die Länge des Höhenarrays.
• Stapel: Ein leerer Stapel, der zum Speichern der Indizes der Histogrammbalken verwendet wird.
• max: Eine Variable, um die bisher gefundene maximale Rechteckfläche zu verfolgen.
• h: Die Höhe des Balkens, der vom Stapel genommen wird.
• w: Die Breite des mit der Höhe h gebildeten Rechtecks.

2. Iterate Through Heights Array

Wir durchlaufen das Höhenarray von links nach rechts und fügen am Ende des Arrays außerdem einen letzten virtuellen Balken mit der Höhe 0 hinzu, um sicherzustellen, dass alle Balken verarbeitet werden.

Schritte in der Iteration:

• Index des aktuellen Balkens verschieben: Für jeden Balken den Index auf den Stapel verschieben. Bevor wir das tun, müssen wir jedoch sicherstellen, dass der aktuelle Balken höher ist als der Balken am Index, der oben im Stapel gespeichert ist. Ist dies nicht der Fall, entfernen wir Balken aus dem Stapel, um die Fläche der Rechtecke zu berechnen, die gebildet werden können, indem wir den Balken am entnommenen Index als kleinsten Balken verwenden (d. h. die Höhe des Rechtecks).

• Aus Stapel entnehmen und Bereich berechnen:

  • Nehmen Sie den obersten Index vom Stapel. Dieser Index stellt die Höhe des kleinsten Balkens im Rechteck dar.
  • Berechnen Sie die Breite des Rechtecks. Wenn der Stapel nach dem Öffnen leer ist, bedeutet dies, dass der entfernte Balken der bisher kleinste war und seine Breite vom Anfang des Arrays bis zum aktuellen Index reicht. Andernfalls wird die Breite durch den Abstand zwischen dem aktuellen Index und dem Index, der sich jetzt oben im Stapel befindet, minus eins, bestimmt.
  • Berechnen Sie die Fläche des Rechtecks ​​anhand der Höhe und Breite und aktualisieren Sie die Variable max, wenn diese Fläche größer ist.

3. Verbleibende Balken im Stapel verarbeiten

Nachdem alle Balken durchlaufen wurden, sind möglicherweise noch einige Balken im Stapel übrig. Diese Balken hätten Höhen, die nicht verarbeitet wurden, da rechts kein kürzerer Balken vorhanden war. Wir müssen diese verbleibenden Balken auf ähnliche Weise verarbeiten, indem wir sie vom Stapel nehmen und die Fläche berechnen.

Detaillierte Erläuterung des Kodex

Hier ist der JavaScript-Code mit Kommentaren, die jeden Teil erläutern:

/**
 * @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;
};

Komplexitätsanalyse

• Zeitkomplexität: O(n), wobei n die Anzahl der Balken im Histogramm ist. Jeder Balken wird höchstens einmal vom Stapel geschoben und entfernt.
• Raumkomplexität:O(n) für den Stapel, der zum Verfolgen von Indizes verwendet wird.

Das obige ist der detaillierte Inhalt vonGrößtes Rechteck im Histogramm. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!