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

Es gibt auch eine andere Lösung mit Divide et Conquer. Der Algorithmus dafür lautet :

1) Teilen Sie das Feld in 2 Teile, wobei die kleinste Höhe die Sollbruchstelle darstellt.

2) Die maximale Fläche ist das Maximum von : a) Kleinste Höhe * Größe des Feldes b) Maximales Rechteck im linken Halbfeld c) Maximales Rechteck in der rechten Hälfte des Feldes

Die Zeitkomplexität beträgt O(nlogn)

Answer 2

Die Stapellösung ist eine der cleversten Lösungen, die ich bis heute gesehen habe. Und es kann ein bisschen schwer zu verstehen sein, warum das funktioniert.

Ich habe versucht, das Gleiche im Detail zu erklären ici .

Zusammenfassung der Punkte aus dem Beitrag:-

• Die allgemeine Denkweise unseres Gehirns ist :-
  • Erstellen Sie jede Situation und versuchen Sie, den Wert der Einschränkung zu finden, der zur Lösung des Problems erforderlich ist.
  • Und wir wandeln das fröhlich in Code um als: - Finde den Wert von contraint(min) für jede Situation(pair(i,j))

Die cleveren Lösungen versuchen, das Problem umzukehren. Für jede constraint/min Wert der Fläche, was ist der bestmögliche linke und rechte Rand?

• Wenn wir also über jede mögliche min in der Anordnung. Was sind die linken und rechten Extremwerte für jeden Wert?

  • Ein kleiner Gedanke besagt, dass der erste linke Wert geringer ist als der current min und in ähnlicher Weise den ersten Wert ganz rechts, der kleiner ist als der aktuelle Mindestwert.

• Jetzt müssen wir sehen, ob wir einen geschickten Weg finden können, um die ersten linken und rechten Werte zu finden, die kleiner als der aktuelle Wert sind.

• Nachdenken : Wenn wir das Feld teilweise durchlaufen haben, sagen wir bis min_i, wie kann die Lösung für min_i+1 gebildet werden?

• Wir brauchen den ersten Wert links von min_i, der kleiner ist als er.

• Umkehrung der Aussage: Wir müssen alle Werte links von min_i ignorieren, die größer als min_i sind. Wir hören auf, wenn wir den ersten Wert finden, der kleiner als min_i (i) ist. Die Talsohlen der Kurve werden also nutzlos, wenn wir sie durchschritten haben. . Im Histogramm, (2 4 3) => wenn 3 min_i ist, ist 4 größer und nicht von Interesse.

• Korrollar : in einem Bereich (i,j). j ist der Mindestwert, den wir betrachten alle Werte zwischen j und seinem linken Wert i sind nutzlos. Auch für weitere Berechnungen.

• Jedes Histogramm auf der rechten Seite, dessen Minimalwert größer als j ist, wird an j gebunden. Die interessierenden Werte auf der linken Seite bilden eine monoton ansteigende Folge, wobei j der größte Wert ist. (Interessante Werte sind hier mögliche Werte, die für das spätere Array von Interesse sein könnten)

• Da wir uns von links nach rechts bewegen, wissen wir bei jedem Minimalwert/jedem aktuellen Wert nicht, ob auf der rechten Seite des Arrays ein kleineres Element vorhanden sein wird.

  • Wir müssen ihn also im Speicher behalten, bis wir wissen, dass dieser Wert nutzlos ist. (da ein kleinerer Wert gefunden wird)

• All dies führt zu einer Verwendung unserer eigenen stack Struktur.

  • Wir stapeln so lange, bis wir nicht mehr wissen, dass es sinnlos ist.
  • Wenn wir wissen, dass die Sache Mist ist, nehmen wir sie vom Stapel.

• Um für jeden Minimalwert seinen linken kleineren Wert zu finden, gehen wir wie folgt vor:-

  1. die Elemente größer zu machen (unbrauchbare Werte)
  2. Das erste Element, das kleiner als der Wert ist, ist das linke Ende. Das i zu unserem min.

• Wir können das Gleiche von der rechten Seite des Arrays aus tun und erhalten j bis zu unserem Minimum.

Es ist ziemlich schwierig, dies zu erklären, aber wenn es Sinn macht, empfehle ich, den gesamten Artikel zu lesen ici da sie mehr Einblicke und Details enthält.

Answer 3

Die anderen Einträge verstehe ich nicht, aber ich glaube, ich weiß, wie man es in O(n) wie folgt machen kann.

A) Finde für jeden Index das größte Rechteck innerhalb des Histogramms, das bei diesem Index endet, wobei die Indexspalte den oberen Rand des Rechtecks berührt, und merke dir, wo das Rechteck beginnt. Dies kann mit einem stapelbasierten Algorithmus in O(n) erledigt werden.

B) Finde in ähnlicher Weise für jeden Index das größte Rechteck, das bei diesem Index beginnt und bei dem die Indexspalte den oberen Rand des Rechtecks berührt, und merke dir, wo das Rechteck endet. Auch O(n) mit der gleichen Methode wie (A), aber Scannen des Histogramms rückwärts.

C) Kombiniere für jeden Index die Ergebnisse von (A) und (B), um das größte Rechteck zu bestimmen, bei dem die Spalte bei diesem Index den oberen Rand des Rechtecks berührt. O(n) wie (A).

D) Da das größte Rechteck von einer Spalte des Histogramms berührt werden muss, ist das größte Rechteck das in Schritt (C) gefundene größte Rechteck.

Der schwierige Teil ist die Umsetzung von (A) und (B), was meiner Meinung nach eher das Problem ist, das JF Sebastian gelöst hat, als das allgemeine Problem.

Answer 4

Ich habe diesen codiert und fühlte mich etwas besser:

import java.util.Stack;

     class StackItem{
       public int sup;
       public int height;
       public int sub;

       public StackItem(int a, int b, int c){
           sup = a;
           height = b;
           sub =c;
       }
       public int getArea(){
           return (sup - sub)* height;
       }

       @Override
       public String toString(){
       return "     from:"+sup+
              "     to:"+sub+
              "     height:"+height+              
              "     Area ="+getArea();
       }
    }   

public class MaxRectangleInHistogram {    
    Stack<StackItem> S;
    StackItem curr;
    StackItem maxRectangle;

    public StackItem getMaxRectangleInHistogram(int A[], int n){
        int i = 0;
        S = new Stack();        
        S.push(new StackItem(0,0,-1));
        maxRectangle = new StackItem(0,0,-1);

        while(i<n){

                curr = new StackItem(i,A[i],i);

                    if(curr.height > S.peek().height){
                            S.push(curr); 
                    }else if(curr.height == S.peek().height){                            
                            S.peek().sup = i+1;                         
                    }else if(curr.height < S.peek().height){                            

                            while((S.size()>1) && (curr.height<=S.peek().height)){
                                curr.sub = S.peek().sub;
                                S.peek().sup = i;
                                decideMaxRectangle(S.peek());
                                S.pop(); 
                            }                               
                        S.push(curr);                    
                    }
            i++;
        }

        while(S.size()>1){ 
            S.peek().sup = i;
            decideMaxRectangle(S.peek());
            S.pop();            
        }  

        return maxRectangle;
    }

    private void decideMaxRectangle(StackItem s){ 

        if(s.getArea() > maxRectangle.getArea() )
            maxRectangle = s;      
    }

}

Nur Hinweis:

Time Complexity: T(n) < O(2n) ~ O(n)
Space Complexity S(n) < O(n)

Answer 5

Ich möchte mich bei @templatetypedef für seine/ihre äußerst detaillierte und intuitive Antwort bedanken. Der folgende Java-Code basiert auf seinem Vorschlag, kartesische Bäume zu verwenden, und löst das Problem in O(N) Zeit und O(N) Raum. Ich schlage vor, dass Sie die obige Antwort von @templatetypedef lesen, bevor Sie den folgenden Code lesen. Der Code ist im Format der Lösung des Problems bei leetcode angegeben: https://leetcode.com/problems/largest-rectangle-in-histogram/description/ und besteht alle 96 Testfälle.

class Solution {

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

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

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

    if (low == high) {
        if(0 <= low && low <= nums.length - 1) {
            return nums[low];
        }
        return 0;
    }

    /* Assume the Cartesian tree nodes are annotated with their
     * positions in the original array.
     */
    int leftArea = -1 , rightArea= -1;
    if(root.left != null) {
        leftArea = largestRectangleUnder(low, root.index - 1 , root.left, nums);
    }
    if(root.right != null) {
        rightArea = largestRectangleUnder(root.index + 1, high,root.right, nums);
    }
    return Math.max((high - low  + 1) * root.val, 
           Math.max(leftArea, rightArea));
}

public int largestRectangleArea(int[] heights) {
    if(heights == null || heights.length == 0 ) {
        return 0;
    }
    if(heights.length == 1) {
        return heights[0];
    }
    Node root = getCartesianTreeFromArray(heights);
    return largestRectangleUnder(0, heights.length - 1, root, heights);
}

}