Dieser Artikel untersucht hauptsächlich den Inhalt im Zusammenhang mit den größten Submatrix in Java -Programmierarrays, wie unten beschrieben.
Ein guter Mensch zu treffen kann Ihr Leben verändern. Ein gutes Buch treffen, nicht wahr?
Vor kurzem hatte ich viele Einblicke, als ich Herrn Zuo Chengyuns " die optimalen Lösungen für den Algorithmus- und Datenstrukturfragen des Programmiercode -Interviewhandbuchs " las. Es wird empfohlen, dass auch Blogger, die Hobbys in diesem Bereich haben, auch zuschauen.
Der Algorithmus der größten Matrix des in dem Buch erläuterten Stack-basierten Array ist sehr klassisch, aber der Blogger hat eine begrenzte Fähigkeit und konnte die Essenz des Algorithmus nicht gründlich verstehen. Aufgrund dieser Idee hat der Blogger jedoch einen einfachen Algorithmus für diese Art von Problem entwickelt, die wie folgt zusammengefasst ist.
Kernidee
Schauen wir uns zuerst ein Bild an und wir können es grob verstehen.
Wie in der Abbildung gezeigt, ist jede Runde eine Operation und unser Kern ist der interne Betrieb für jede Runde.
Berechnen Sie die maximale Länge jeder Schicht kontinuierlich und ununterbrochen
Mit anderen Worten, wir sind das wichtigste Array, um den Boden bis Oberrunde zu berechnen, und dann können wir den Bereich der kontinuierlichen maximalen Submatrix berechnen, die für jede Runde in dieser Runde erhalten werden kann. Dann müssen Sie nur die größten Daten für jede Runde vergleichen und zurückkehren, um den Bereich der größten kontinuierlichen Submatrix des Arrays zu finden.
Code
Okay, mit den oben genannten Kernideen können wir mit dem Schreiben von Code beginnen. (Obwohl ich nicht glaube, dass ich es ganz klar gesagt habe, vergib mir bitte).
Paket stack_and_queue;/*** @Author Guo pu <br>* Berechnen Sie den Bereich des größten kontinuierlichen Rechteckbereichs basierend auf der Array*/öffentliche Klasse MaxRectangle {public static void main (String [] args) {integer [] arr = {2, 1, 3, 5, 7, 6, 4}; maxRectangleArea(arr);System.out.println("The area of the largest continuous rectangle area in the array is: " + maxRectangle);}/** * @param arr * @return The maximum area of the continuous rectangle area in the array*/private static Integer maxRectangleArea(Integer[] arr) {int[] result = new int [arr.length]; // Berechnen Sie das Array, indem Sie die kontinuierliche Länge von unten nach oben durchqueren (int i = 1; i <= arr.länge; i ++) {// Der temporäre Wert der akkumulierten kontinuierlichen Länge in der aktuellen Runde wird in der Höhe von Temple implementiert. Das erste Schicht -Index führt den Verlust des vorherigen Teils der Daten für (int j = 1; j <= arr.length; j ++) {if (arr [j - 1]> = i) {TempEN += 1; templen_max = tempolen;} else {Templlen = 0; "Die maximale kontinuierliche und ununterbrochene Länge der Schicht lautet:"+tempplen_max);} // Die Zahl mit dem größten numerischen Wert im Ergebnis -Set -Array finden, dh der Bereich der größten rechteckigen Domäne in der Kontinuitätsfläche in Int MaxArea = 0; für (int i = 0; Ergebnis [i];} // Zurück den Bereich des maximalen kontinuierlichen Rechteckfeldes, das durch Rückkehr von MaxArea erhalten wird;}}Die Kommentare im Code sind ebenfalls relativ umfassend, daher werde ich nicht zu viel Details eingehen.
prüfen
Das Folgende ist ein Test des Arrays. Testen wir es zunächst mit dem im Bild angezeigten Array am Anfang dieses Artikels.
Integer [] arr = {2,1,3,5,7,6,4} ・・・・Der Bereich des größten kontinuierlichen rechteckigen Bereichs in der Array ist: 16
Anschließend ändern wir die Werte von Elementen im Array, um weiter zu testen, ob die Ergebnisse korrekt sind.
Integer [] arr = {2,1,3,1,7,6,4} ・・・・Der Bereich des größten kontinuierlichen rechteckigen Bereichs in der Array ist: 12
Nachdem der Blogger selbst es getestet hat, funktioniert der Algorithmus normal. :)
Optimierungsteil
Wenn wir über den Optimierungsteil sprechen, können wir als erstes den Maximalwert im Ergebnis -Set -Array im letzten Schritt sehen.
In der Tat können wir tatsächlich eine weitere Variable anwenden, um den Bereich der bisher größten Submatrix der Runde aufzuzeichnen. Diese Optimierung spielt jedoch keine große Rolle und es gibt keine signifikante Verbesserung der Zeitkomplexität.
Ein weiterer Punkt: Ich denke, der bessere Einstiegspunkt besteht darin, ein Urteilsvermögen bei der Durchführung von Berechnungen für jede Runde hinzuzufügen, um zu entscheiden, ob sie vor der aktuellen Runde nach unten fahren sollen. Wenn die Elemente im Array stark schwanken, ist die Optimierungsstufe immer noch sehr gut.
Zusammenfassen
Dieser kleine Algorithmus ist exquisiter, und das einzige, was fehlerhafter ist, ist, dass die zeitliche Komplexität etwas intensiver ist. Wenn Leser nach einem Algorithmus mit einer relativ geringen Komplexität suchen, machen Sie bitte einen Umweg.
Es ist ziemlich gut, wenn Sie nur ein Ergebnis finden möchten. Zumindest ist es viel effizienter als die gewalttätige Computermethode.
Das obige ist der gesamte Inhalt dieses Artikels über die einfache Lösung für die maximale Submatrix in Java -Programmierarrays. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!