In einer kürzlichen Interviewfrage habe ich folgendes Problem bekommen.
In einer bestimmten Stadt haben wir eine Reihe von Gebäuden mit unterschiedlichen Höhen. Der Einsturz eines Gebäudes mit der Höhe h bewirkt, dass die nächsten h-1 Gebäude rechts ebenfalls kollabieren. Die Höhe der Gebäude kann zwischen 1 und 5000 liegen. Angesichts der Höhen aller Gebäude (von links nach rechts angeordnet; dh für den Index des linken Gebäudes = 1 und für den Index des Gebäudes ganz rechts = N) mussten wir den Index des Gebäude, das die maximale Zerstörung verursachen würde.
Zum Beispiel:
Eingabe: Anzahl der Gebäude: 6
Höhe der Gebäude: 2 1 3 3 1 6
Antwort sollte am Index 3
aufbauenDie Lösung, die ich versuchte, war die Brute-Force-Technik mit einer Komplexität von O (N ^ 2). Was ich getan habe, war für jedes Gebäude in der Liste die Anzahl der Gebäude, die es zerstören würde.
Könnte eine bessere Lösung für diese Frage konstruiert werden?
Geht einfach von links nach links, kollabiert das erste Gebäude und berechnet, wie viel (*) er insgesamt geschädigt hat.
Mach das immer wieder vom nächsten Gebäude (das nicht kollabiert ist).
Wählen Sie hier das Maximum.
Komplexität: O (n).
Dieser gierige Algorithmus funktioniert, weil der ganze Prozess eine Kettenreaktion ist, wenn Gebäude A den Kollaps von B erzwingt, dann kann man von B aus keine bessere Punktzahl erreichen.
(*) Sie können dies tun, indem Sie einen Zähler beibehalten, der speichert, wie viele Gebäude auf der rechten Seite zusammengelegt werden sollen. counter = max(counter - 1, height of next building) .
Einige Bereiche der Stadt fungieren als "Firewalls" - der Kollaps endet an diesem Punkt. ein kleiner Gedanke zeigt, dass dies Abschnitte links von einem Wert von 1 sind, wo die Höhe nicht mehr als einmal pro Schritt zunimmt (wenn Sie 0 Höhen haben können, die die Dinge sehr leicht verkomplizieren).
und die Region mit der höchsten Punktzahl muss direkt nach einer Firewall beginnen (da es andernfalls eine höhere Region nur auf der linken Seite geben würde).
Scanne also von rechts, finde diese Firewalls und finde dann heraus, welcher Bereich rechts von einer Firewall den größten Schaden hat. das ist O (n), weil es nur lineare Scans sind (einmal von rechts nach links und dann einmal für jeden Abschnitt, ohne Überlappung).
Eigentlich ist Karoly's Antwort gleichwertig und einfacher zu implementieren.Etwas wie (Verwüstung von Gebäude I)
%Vor% In Java, ohne nachfolgende Kollabierungen zu berücksichtigen:
Meine endgültige Lösung unterscheidet sich von der akzeptierten Lösung, die ich übrigens nicht vollständig verstanden habe. Die Idee ist, ausgehend von der Position ganz rechts die Anzahl der Gebäude zu zählen, die der aktuelle Index zusammenbrechen lässt.
%Vor%Dann mache ich einfach eine kumulative Summe, beginnend wieder von ganz rechts. Ich füge zur Anzahl der Gebäude hinzu, die aktuelle Position kollabiert die Anzahl der Gebäude, die zusammengestürzt sind und vom nächsten Gebäude nach rechts starren, das bis zum Ende nicht zusammenbrach.
%Vor%Am Ende gebe ich nur den Index mit dem maximalen Schaden zurück.
Diese Lösung wird in O(n) ausgeführt, verwendet jedoch ein zusätzliches O(n) Leerzeichen.
Der nächste Code ist die vollständige Version (funktioniert auch für nachfolgende Zusammenbrüche):
%Vor%Tags und Links algorithm