Maximieren Sie den rechteckigen Bereich unter Histogramm

Question

Ich habe ein Histogramm mit ganzzahligen Höhen und konstanter Breite 1. Ich möchte die rechteckige Fläche unter einem Histogramm maximieren. z.B.:

 _
| |
| |_ 
|   |
|   |_
|     |

Die Antwort auf diese Frage wäre 6, 3 * 2, unter Verwendung von col1 und col2.

O(n^2) brute force ist mir klar, ich möchte einen O(n log n) Algorithmus. Ich versuche, dynamisches Programmieren im Sinne eines O(n log n)-Algorithmus mit maximal ansteigender Teilfolge zu verstehen, aber ich komme nicht weiter. Sollte ich einen Divide-and-Conquer-Algorithmus verwenden?

PS: Personen, die über ein ausreichendes Ansehen verfügen, werden gebeten, die Markierung "Teile und herrsche" zu entfernen, wenn es keine solche Lösung gibt.

Nach den Kommentaren von mho: Ich meine die Fläche des größten Rechtecks, das vollständig hineinpasst. (Danke j_random_hacker für die Klarstellung :) ).

Answer 1

Die obigen Antworten haben die beste O(n)-Lösung in Code gegeben, allerdings sind ihre Erklärungen ziemlich schwer zu verstehen. Der O(n)-Algorithmus, der einen Stapel verwendet, erschien mir zunächst magisch, aber jetzt ergibt er für mich einen Sinn. OK, lassen Sie mich das erklären.

Erste Beobachtung:

Um das maximale Rechteck zu finden, muss man für jeden Balken x kennen wir den ersten kleineren Balken auf jeder Seite, sagen wir l y r sind wir sicher, dass height[x] * (r - l - 1) ist die beste Chance, die wir mit der Höhe des Balkens bekommen können x . In der folgenden Abbildung sind 1 und 2 die ersten kleineren von 5.

OK, nehmen wir an, wir können dies in O(1) Zeit für jeden Balken tun, dann können wir dieses Problem in O(n)! lösen, indem wir jeden Balken scannen.

Dann stellt sich die Frage: Können wir wirklich für jeden Balken den ersten kleineren Balken links und rechts von ihm in O(1) Zeit finden? Das scheint unmöglich, oder? ... Es ist möglich, indem man einen wachsenden Stapel verwendet.

Warum kann man mit einem aufsteigenden Stapel den ersten kleineren links und rechts davon im Auge behalten?

Vielleicht ist es nicht überzeugend, wenn ich Ihnen sage, dass ein wachsender Stapel die Arbeit erledigen kann, also werde ich Ihnen dies erläutern.

Erstens brauchen wir eine Operation, damit der Stapel weiter wächst:

while x < stack.top():
    stack.pop()
stack.push(x)

Dann können Sie überprüfen, dass in dem wachsenden Stapel (wie unten dargestellt), für stack[x] , stack[x-1] das erste kleinere Element auf der linken Seite ist, dann ein neues Element, das aufspringen kann stack[x] out ist die erste kleinere auf der rechten Seite.

Kannst du immer noch nicht glauben, dass Stapel[x-1] der erste kleinere links auf Stapel[x] ist?

Ich werde es durch Widersprüche beweisen.

Zuallererst, stack[x-1] < stack[x] ist sicher. Aber nehmen wir mal an stack[x-1] ist nicht das erste kleinere links von stack[x] .

Wo ist also die erste kleinere fs ?

If fs < stack[x-1]:
    stack[x-1] will be popped out by fs,
else fs >= stack[x-1]:
    fs shall be pushed into stack,
Either case will result fs lie between stack[x-1] and stack[x], which is contradicting to the fact that there is no item between stack[x-1] and stack[x].

Daher muss Stapel[x-1] der erste kleinere sein.

Zusammenfassung:

Durch die Vergrößerung des Stapels kann für jedes Element der erste kleinere Wert auf der linken und rechten Seite festgehalten werden. Durch diese Eigenschaft kann das maximale Rechteck im Histogramm mit Hilfe eines Stapels in O(n) gelöst werden.

Herzlichen Glückwunsch! Das ist wirklich ein schwieriges Problem. Ich bin froh, dass meine prosaische Erklärung dich nicht davon abgehalten hat, die Aufgabe zu lösen. Anbei ist meine bewährte Lösung als Belohnung :)

def largestRectangleArea(A):
    ans = 0
    A = [-1] + A
    A.append(-1)
    n = len(A)
    stack = [0]  # store index

    for i in range(n):
        while A[i] < A[stack[-1]]:
            h = A[stack.pop()]
            area = h*(i-stack[-1]-1)
            ans = max(ans, area)
        stack.append(i)
    return ans

Answer 2

Neben dem Brute-Force-Ansatz gibt es drei Möglichkeiten, dieses Problem zu lösen. Ich werde sie alle aufschreiben. Die Java-Codes haben Tests auf einer Online-Richter-Website namens leetcode bestanden: http://www.leetcode.com/onlinejudge#question_84 . also bin ich zuversichtlich, dass die Codes korrekt sind.

Lösung 1: dynamische Programmierung + n*n Matrix als Cache

Zeit: O(n^2), Raum: O(n^2)

Grundidee: Verwenden Sie die n*n-Matrix dp[i][j], um die minimale Höhe zwischen bar[i] und bar[j] zwischenzuspeichern. Füllen Sie die Matrix mit Rechtecken der Breite 1.

public int solution1(int[] height) {

    int n = height.length;
    if(n == 0) return 0;
    int[][] dp = new int[n][n];        
    int max = Integer.MIN_VALUE;

    for(int width = 1; width <= n; width++){

        for(int l = 0; l+width-1 < n; l++){

            int r = l + width - 1;

            if(width == 1){
                dp[l][l] = height[l];
                max = Math.max(max, dp[l][l]);
            } else {                    
                dp[l][r] = Math.min(dp[l][r-1], height[r]);
                max = Math.max(max, dp[l][r] * width);
            }                
        }
    }

    return max;
}

Lösung 2: dynamische Programmierung + 2 Arrays als Cache .

Zeit: O(n^2), Raum: O(n)

Grundidee: Diese Lösung ist wie Lösung 1, spart aber etwas Platz. Die Idee ist, dass wir in Lösung 1 die Matrix von Zeile 1 bis Zeile n aufbauen. Aber in jeder Iteration trägt nur die vorherige Zeile zum Aufbau der aktuellen Zeile bei. Wir verwenden also abwechselnd zwei Arrays als vorherige Zeile und aktuelle Zeile.

public int Solution2(int[] height) {

    int n = height.length;
    if(n == 0) return 0;

    int max = Integer.MIN_VALUE;

    // dp[0] and dp[1] take turns to be the "previous" line.
    int[][] dp = new int[2][n];      

    for(int width = 1; width <= n; width++){

        for(int l = 0; l+width-1 < n; l++){

            if(width == 1){
                dp[width%2][l] = height[l];
            } else {
                dp[width%2][l] = Math.min(dp[1-width%2][l], height[l+width-1]);                     
            }
            max = Math.max(max, dp[width%2][l] * width);   
        }
    }        
    return max;
}

Lösung 3: Stapel verwenden .

Zeit: O(n), Platz:O(n)

Diese Lösung ist knifflig, und ich habe gelernt, wie man das macht, und zwar von Erklärung ohne Diagramme y Erklärung mit Diagrammen . Ich schlage vor, dass Sie die beiden Links lesen, bevor Sie meine folgende Erklärung lesen. Es ist schwer zu erklären, ohne Diagramme, so dass meine Erklärungen schwer zu folgen sein könnte.

Im Folgenden finden Sie meine Erläuterungen:

1. Für jeden Balken müssen wir das größte Rechteck finden, das diesen Balken enthält. Gesucht ist also das größte der n Rechtecke.

2. Um das größte Rechteck für einen bestimmten Balken (sagen wir Balken[i], den (i+1)-ten Balken) zu erhalten, müssen wir nur das größte Intervall herausfinden das diesen Balken enthält. Wir wissen, dass alle Balken in diesem Intervall mindestens die gleiche Höhe wie Balken[i] haben müssen. Wenn wir also herausfinden, wie viele wie viele aufeinanderfolgende Balken gleicher oder höherer Höhe sich unmittelbar links von Balken[i] befinden und wie viele aufeinanderfolgende Balken gleicher oder höherer Höhe sich unmittelbar rechts von Balken[i] befinden, wissen wir die Länge des Intervalls, also die Breite des größten Rechtecks für Balken[i].

3. Um die Anzahl der aufeinanderfolgenden Takte gleicher oder höherer Höhe unmittelbar links von Takt[i] zu zählen, müssen wir nur den nächstgelegenen Takt auf der linken Seite finden, der kürzer ist der kürzer ist als Balken[i], da alle Balken zwischen diesem Balken und Balken[i] aufeinanderfolgende Balken gleicher oder höherer Höhe sind.

4. Wir verwenden einen Stapel, um alle linken Balken, die kürzer als ein bestimmter Balken sind, dynamisch zu erfassen. Mit anderen Worten: Wenn wir vom ersten Balken bis zu Balken[i] iterieren, aber gerade bei Balken[i] angekommen sind und den Stapel noch nicht aktualisiert haben, sollte der Stapel alle Takte speichern, die nicht höher als bar[i-1] sind, einschließlich bar[i-1] selbst. Wir vergleichen die Höhe von bar[i] mit jedem Balken im Stapel, bis wir einen finden, der kürzer ist als bar[i], d.h. den kürzesten Balken. Wenn der Balken[i] höher ist als alle Balken im Stapel, bedeutet dies, dass alle Balken links von Balken[i] höher sind als Balken[i].

5. Wir können dasselbe auf der rechten Seite des i-ten Balkens tun. Dann wissen wir für bar[i], wie viele Takte in dem Intervall liegen.

   public int solution3(int[] height) {
   
       int n = height.length;
       if(n == 0) return 0;
   
       Stack<Integer> left = new Stack<Integer>();
       Stack<Integer> right = new Stack<Integer>();
   
       int[] width = new int[n];// widths of intervals.
       Arrays.fill(width, 1);// all intervals should at least be 1 unit wide.
   
       for(int i = 0; i < n; i++){
           // count # of consecutive higher bars on the left of the (i+1)th bar
           while(!left.isEmpty() && height[i] <= height[left.peek()]){
               // while there are bars stored in the stack, we check the bar on the top of the stack.
               left.pop();                
           }
   
           if(left.isEmpty()){
               // all elements on the left are larger than height[i].
               width[i] += i;
           } else {
               // bar[left.peek()] is the closest shorter bar.
               width[i] += i - left.peek() - 1;
           }
           left.push(i);
       }
   
       for (int i = n-1; i >=0; i--) {
   
           while(!right.isEmpty() && height[i] <= height[right.peek()]){                
               right.pop();                
           }
   
           if(right.isEmpty()){
               // all elements to the right are larger than height[i]
               width[i] += n - 1 - i;
           } else {
               width[i] += right.peek() - i - 1;
           }
           right.push(i);
       }
   
       int max = Integer.MIN_VALUE;
       for(int i = 0; i < n; i++){
           // find the maximum value of all rectangle areas.
           max = Math.max(max, width[i] * height[i]);
       }
   
       return max;
   }

Answer 3

Die anderen Antworten hier haben die O(n)-Zeit- und O(n)-Raum-Lösung mit zwei Stapeln gut dargestellt. Es gibt noch eine andere Perspektive auf dieses Problem, die unabhängig davon eine O(n)-Zeit- und O(n)-Raum-Lösung für das Problem bietet und vielleicht ein wenig mehr Einsicht darüber gibt, warum die stapelbasierte Lösung funktioniert.

Der Grundgedanke ist die Verwendung einer Datenstruktur namens Kartesischer Baum . Ein kartesischer Baum ist eine binäre Baumstruktur (allerdings keine binäre Suche Baum), der um ein Eingabefeld herum aufgebaut ist. Insbesondere wird die Wurzel des kartesischen Baums über dem minimalen Element des Arrays aufgebaut, und die linken und rechten Teilbäume werden rekursiv aus den Unterarrays links und rechts des minimalen Werts konstruiert.

Hier ein Beispiel für ein Array und seinen kartesischen Baum:

                 +----------------------- 23 ------+
                 |                                 |
  +------------- 26 --+                        +-- 79
  |                   |                        |
  31 --+              53 --+                   84
       |                   |
       41 --+              58 -------+
            |                        |
            59                  +-- 93
                                |
                                97

+----+----+----+----+----+----+----+----+----+----+----+
| 31 | 41 | 59 | 26 | 53 | 58 | 97 | 93 | 23 | 84 | 79 |
+----+----+----+----+----+----+----+----+----+----+----+

Der Grund, warum kartesische Bäume bei diesem Problem nützlich sind, ist, dass die vorliegende Frage eine wirklich schöne rekursive Struktur hat. Beginnen Sie damit, das unterste Rechteck im Histogramm zu betrachten. Es gibt drei Möglichkeiten, wo das maximale Rechteck am Ende platziert werden könnte:

• Er könnte direkt unter dem Mindestwert im Histogramm liegen. In diesem Fall sollten wir ihn so breit wie das gesamte Array machen, um ihn so groß wie möglich zu machen.

• Er könnte ganz links vom Mindestwert liegen. In diesem Fall wollen wir rekursiv die Antwort aus dem Subarray rein links vom Minimalwert gebildet haben.

• Er könnte ganz rechts vom Mindestwert liegen. In diesem Fall wollen wir rekursiv die Antwort aus dem Subarray rein rechts vom Minimalwert gebildet haben.

Beachten Sie, dass diese rekursive Struktur - den Minimalwert finden, etwas mit den Unterfeldern links und rechts von diesem Wert tun - perfekt der rekursiven Struktur eines kartesischen Baums entspricht. Wenn wir zu Beginn einen kartesischen Baum für das gesamte Array erstellen können, können wir das Problem lösen, indem wir den kartesischen Baum von der Wurzel abwärts rekursiv durchlaufen. An jedem Punkt berechnen wir rekursiv das optimale Rechteck in den linken und rechten Subarrays, zusammen mit dem Rechteck, das man erhält, wenn man es direkt unter den Minimalwert einpasst, und geben dann die beste Option zurück, die wir finden.

In Pseudocode sieht das folgendermaßen aus:

function largestRectangleUnder(int low, int high, Node root) {
  /* Base case: If the range is empty, the biggest rectangle we
   * can fit is the empty rectangle.
   */
  if (low == high) return 0;

  /* Assume the Cartesian tree nodes are annotated with their
   * positions in the original array.
   */
  return max {
    (high - low) * root.value, // Widest rectangle under the minimum
    largestRectangleUnder(low,            root.index, root.left),
    largestRectnagleUnder(root.index + 1, high,       root.right)
  }
}

Sobald wir den kartesischen Baum haben, benötigt dieser Algorithmus O(n) Zeit, da wir jeden Knoten genau einmal besuchen und O(1) Arbeit pro Knoten erledigen.

Es stellt sich heraus, dass es einen einfachen Algorithmus mit linearer Zeit für den Aufbau kartesischer Bäume gibt. Die "natürliche" Art und Weise, einen solchen Baum zu erstellen, wäre, das Array zu scannen, den Minimalwert zu finden und dann rekursiv einen kartesischen Baum aus den linken und rechten Subarrays zu erstellen. Das Problem ist, dass die Suche nach dem Minimalwert sehr teuer ist und viel Zeit in Anspruch nehmen kann (n 2 ).

Der "schnelle" Weg, einen kartesischen Baum zu erstellen, besteht darin, das Array von links nach rechts zu durchsuchen und ein Element nach dem anderen hinzuzufügen. Dieser Algorithmus basiert auf den folgenden Beobachtungen über kartesische Bäume:

• Erstens gehorchen kartesische Bäume der Haufeneigenschaft: Jedes Element ist kleiner oder gleich seinen Kindern. Der Grund dafür ist, dass die Wurzel des kartesischen Baums der kleinste Wert im gesamten Array ist, und seine Kinder sind die kleinsten Elemente in ihre Subarrays, usw.

• Zweitens: Wenn Sie einen kartesischen Baum in Reihenfolge durchlaufen, erhalten Sie die Elemente des Arrays in der Reihenfolge zurück, in der sie erscheinen. Um zu sehen, warum das so ist, beachten Sie, dass Sie bei einer inorder Traversierung eines kartesischen Baumes zuerst alles links vom Minimalwert besuchen, dann den Minimalwert, dann alles rechts vom Minimalwert. Diese Besuche werden rekursiv auf die gleiche Weise durchgeführt, so dass am Ende alles in der richtigen Reihenfolge besucht wird.

Diese beiden Regeln geben uns eine Menge Informationen darüber, was passiert, wenn wir mit einem kartesischen Baum der ersten k Elemente des Arrays beginnen und einen kartesischen Baum für die ersten k+1 Elemente bilden wollen. Das neue Element muss auf dem rechten Rückgrat des kartesischen Baums landen - dem Teil des Baums, der gebildet wird, indem man bei der Wurzel beginnt und nur Schritte nach rechts macht -, weil sonst etwas in einer inorder traversal nachkommen würde. Und innerhalb dieses rechten Rückgrats muss er so platziert werden, dass er größer ist als alles, was über ihm liegt, da wir die Eigenschaft des Haufens beachten müssen.

Um einen neuen Knoten in den kartesischen Baum einzufügen, beginnt man am äußersten rechten Knoten des Baums und wandert nach oben, bis man entweder die Wurzel des Baums erreicht oder einen Knoten mit einem kleineren Wert findet. Der neue Wert hat dann als linkes Kind den letzten Knoten, über den er nach oben gewandert ist.

Hier ist ein Beispiel für diesen Algorithmus auf einem kleinen Array:

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

2 wird die Wurzel.

  2 --+
      |  
      4

4 ist größer als 2, wir können uns nicht nach oben bewegen. Nach rechts anhängen.

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

  2 ------+
          |
      --- 3 
      |
      4

3 ist kleiner als 4, klettere darüber. Kann nicht weiter über 2 klettern, da sie kleiner als 3 ist. Der überkletterte Teilbaum, der in 4 verwurzelt ist, geht nach links zum neuen Wert 3, und 3 wird jetzt zum ganz rechten Knoten.

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

  +---------- 1
  |
  2 ------+
          |
      --- 3
      |
      4

1 klettert über die Wurzel 2, der gesamte Baum mit der Wurzel 2 wird nach links von 1 verschoben, und 1 ist nun die neue Wurzel - und auch der Wert ganz rechts.

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

Auch wenn es nicht so aussieht, als würde dies in linearer Zeit ablaufen - würde man nicht möglicherweise den ganzen Weg zur Wurzel des Baumes immer und immer wieder zurücklegen? - kann man mit einem cleveren Argument zeigen, dass dies in linearer Zeit abläuft. Wenn Sie während einer Einfügung über einen Knoten in der rechten Wirbelsäule klettern, wird dieser Knoten schließlich aus der rechten Wirbelsäule verschoben und kann daher bei einer zukünftigen Einfügung nicht erneut gescannt werden. Daher wird jeder Knoten höchstens einmal gescannt, so dass die Gesamtarbeit linear ist.

Und jetzt kommt der Clou: Die Standardmethode, mit der Sie diesen Ansatz umsetzen, besteht darin, einen Stapel mit den Werten zu führen, die den Knoten auf der rechten Wirbelsäule entsprechen. Wenn man über einen Knoten geht, wird ein Knoten vom Stapel genommen. Daher sieht der Code zum Aufbau eines kartesischen Baums etwa so aus:

Stack s;
for (each array element x) {
   pop s until it's empty or s.top > x
   push x onto the stack.
   do some sort of pointer rewiring based on what you just did.
}

Die Stapelmanipulationen hier mögen wirklich misslungen erscheinen, und das liegt daran, dass Dies sind genau die Stapeloperationen, die Sie auch in den hier gezeigten Antworten durchführen würden. Man kann sich das, was diese Ansätze bewirken, wie folgt vorstellen implizit den kartesischen Baum aufbauen und dabei den oben gezeigten rekursiven Algorithmus ausführen.

Der Vorteil der Kenntnis kartesischer Bäume liegt meiner Meinung nach darin, dass sie einen sehr guten konzeptionellen Rahmen für die korrekte Funktionsweise dieses Algorithmus bieten. Wenn man weiß, dass man einen rekursiven Spaziergang durch einen kartesischen Baum macht, ist es einfacher zu erkennen, dass man garantiert das größte Rechteck finden wird. Außerdem ist das Wissen um die Existenz des kartesischen Baums ein nützliches Hilfsmittel für die Lösung anderer Probleme. Kartesische Bäume tauchen bei der Entwicklung von schnellen Datenstrukturen für die Bereich-Minimum-Abfrage-Problem und werden verwendet, um die Suffix-Arrays in Suffixbäume .

---

Hier ist ein Java-Code, der diese Idee umsetzt, mit freundlicher Genehmigung von @Azeem!

import java.util.Stack;

public class CartesianTreeMakerUtil {

    private static class Node {
        int val;
        Node left;
        Node right;
    }

    public static Node cartesianTreeFor(int[] nums) {
        Node root = null;
        Stack<Node> s = new Stack<>();
        for(int curr : nums) {
            Node lastJumpedOver = null;
            while(!s.empty() && s.peek().val > curr) {
                lastJumpedOver = s.pop();
            }
            Node currNode = this.new Node();
            currNode.val = curr;
            if(s.isEmpty()) {
                root = currNode;
            }
            else {
                s.peek().right = currNode;
            }
            currNode.left = lastJumpedOver;
            s.push(currNode);
        }
        return root;
    }

    public static void printInOrder(Node root) {
        if(root == null) return;
        if(root.left != null ) {
            printInOrder(root.left);
        }
        System.out.println(root.val);
        if(root.right != null) {
            printInOrder(root.right);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[args.length];
        for (int i = 0; i < args.length; i++) {
            nums[i] = Integer.parseInt(args[i]);
        }
        Node root = cartesianTreeFor(nums);
        tester.printInOrder(root);
    }
}

Answer 4

Implementierung in Python von die Antwort des @IVlad O(n) Lösung:

from collections import namedtuple

Info = namedtuple('Info', 'start height')

def max_rectangle_area(histogram):
    """Find the area of the largest rectangle that fits entirely under
    the histogram.

    """
    stack = []
    top = lambda: stack[-1]
    max_area = 0
    pos = 0 # current position in the histogram
    for pos, height in enumerate(histogram):
        start = pos # position where rectangle starts
        while True:
            if not stack or height > top().height:
                stack.append(Info(start, height)) # push
            elif stack and height < top().height:
                max_area = max(max_area, top().height*(pos-top().start))
                start, _ = stack.pop()
                continue
            break # height == top().height goes here

    pos += 1
    for start, height in stack:
        max_area = max(max_area, height*(pos-start))

    return max_area

Beispiel:

>>> f = max_rectangle_area
>>> f([5,3,1])
6
>>> f([1,3,5])
6
>>> f([3,1,5])
5
>>> f([4,8,3,2,0])
9
>>> f([4,8,3,1,1,0])
9

Lineare Suche mit einem Stapel von unvollständigen Teilproblemen

Kopieren Sie die Beschreibung des Algorithmus (für den Fall, dass die Seite nicht mehr funktioniert):

Wir verarbeiten die Elemente in in der Reihenfolge von links nach rechts und führen einen Stapel von Informationen über begonnene, aber noch nicht beendete Subhistogramme. Wann immer ein neues Element eintrifft, wird es den folgenden Regeln unterworfen. Wenn der Stapel leer ist, eröffnen wir ein neues Teilproblem durch indem wir das Element auf den Stapel schieben. Andernfalls vergleichen wir es mit dem Element oben auf dem Stapel. Wenn das neue Element größer, schieben wir es erneut. Wenn das neue gleich ist, wird es übersprungen. In all diesen Fällen fahren wir mit dem nächsten neuen Element fort. Wenn das neue Element kleiner ist, wird beenden wir das oberste Teilproblem durch Aktualisierung der maximalen Fläche in Bezug auf das Element an der Spitze des Stapels. Dann, wird das oberste Element verworfen, und wiederholen den Vorgang unter Beibehaltung des aktuellen neuen Element. Auf diese Weise werden alle Teilprobleme abgearbeitet, bis der Stapel leer ist, oder sein oberstes Element ist kleiner oder gleich dem neuen Element ist, was zu den folgenden Aktionen führt oben beschriebenen Aktionen. Wurden alle Elemente verarbeitet, und der Stapel ist noch nicht noch nicht leer ist, beenden wir die verbleibenden Teilprobleme durch Aktualisierung der maximalen Fläche in Bezug auf die Elemente an der oben.

Für die Aktualisierung in Bezug auf ein Element wird das größte Rechteck gefunden, das dieses Element einschließt. Beachten Sie, dass eine Aktualisierung der maximalen Fläche erfolgt für alle Elemente durchgeführt wird, außer für diejenigen übersprungen werden. Wenn ein Element übersprungen wird, hat es jedoch die gleiche größte Rechteck wie das Element, das zu diesem Zeitpunkt oben auf dem Stapels zu diesem Zeitpunkt, das dann später aktualisiert wird. Die Höhe des größten Rechteckes ist natürlich der Wert des Elements. Zum Zeitpunkt der der Aktualisierung wissen wir, wie weit das größte Rechteck nach rechts reicht des Elements reicht, denn dann wird zum zum ersten Mal ein neues Element mit kleinerer Höhe hinzugekommen. Die Information, wie weit weit das größte Rechteck nach links links vom Element reicht, ist verfügbar wenn wir sie ebenfalls auf dem Stapel speichern.

Wir überarbeiten daher das Verfahren wie oben beschrieben. Wenn ein neues Element sofort geschoben, entweder weil der Stapel leer ist oder es größer ist als das oberste Element des Stapels, wird das größte Rechteck, das es enthält nach links nicht weiter reicht als das aktuelle Element. Wenn es geschoben wird nachdem bereits mehrere Elemente vom Stapel gepoppt, weil es kleiner als diese Elemente ist, erstreckt sich das größte Rechteck, das es enthält, nach so weit nach links wie das des zuletzt zuletzt gepoppten Elements.

Jedes Element wird bei und in jedem Schritt der Prozedur Prozedur wird mindestens ein Element geschoben oder gepoppt. Da die Menge der Arbeit für die Entscheidungen und die Aktualisierung konstant ist, ist die Komplexität des Algorithmus durch Amortisation O(n) Analyse.

Answer 5

Die einfachste Lösung in O(N)

long long getMaxArea(long long hist[], long long n)
{

    stack<long long> s;

    long long max_area = 0; 
    long long tp;  
    long long area_with_top; 

    long long i = 0;
    while (i < n)
    {
        if (s.empty() || hist[s.top()] <= hist[i])
            s.push(i++);
       else
        {
            tp = s.top();  // store the top index
            s.pop();  // pop the top
            area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
            if (max_area < area_with_top)
            {
                max_area = area_with_top;
            }
        }
    }

   while (!s.empty())
    {
        tp = s.top();
        s.pop();
        area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);

        if (max_area < area_with_top)
            max_area = area_with_top;
    }

    return max_area;
}