Einführung
Du hast vor, in den Wäldern in der Nähe deines Hauses ein Baumhaus zu bauen, damit du den Sonnenaufgang und den Sonnenuntergang beobachten kannst.
Du hast Daten von einem örtlichen Vermessungsbüro erhalten, die die Höhe jedes Baums in jedem rechteckigen Abschnitt der Karte angeben.
Du musst jedes Raster auf der Karte analysieren, um gute Bäume für dein Baumhaus zu finden.
Ein guter Baum erfüllt beides:
- er ist höher als jeder Baum im Osten und Westen, damit du die bestmögliche Sicht auf die Sonnenaufgänge und Sonnenuntergänge hast.
- er ist niedriger als jeder Baum im Norden und Süden, um das Klettern auf Bäume so gering wie möglich zu halten.
Anleitung
Deine Aufgabe ist es, die möglichen Bäume zu finden, in denen du dein Baumhaus bauen könntest.
Die Datenfirma stellt die Daten als Raster bereit, die die Höhen der Bäume anzeigen.
Die Zeilen des Rasters stehen für die Ost-West-Richtung und die Spalten für die Nord-Süd-Richtung.
Ein geeigneter Baum ist der größte in seiner Zeile und gleichzeitig der kleinste in seiner Spalte.
Ein Raster hat vielleicht gar keine geeigneten Bäume.
Oder es hat einen, oder sogar mehrere.
Hier ist ein Raster, in dem es genau einen Kandidaten gibt.
↓
1 2 3 4
|-----------
1 | 9 8 7 8
→ 2 |[5] 3 2 4
3 | 6 6 7 1
- Zeile 2 enthält die Werte 5, 3, 2 und 4. Der größte Wert ist 5.
- Spalte 1 enthält die Werte 9, 5 und 6. Der kleinste Wert ist 5.
Der Punkt bei [2, 1] (Zeile: 2, Spalte: 1) ist also ein prima Platz für ein Baumhaus.
Rust-Indizes beginnen bei 0
Nach Konvention werden die Inhalte geordneter Wertefolgen in Rust ab 0 nummeriert („indexiert"). Das gilt unabhängig davon, was der restliche Text der Übungsbeschreibung in dieser README sagt, etwa Verweise auf Indizes, die bei 1 beginnen. Du musst also 1 abziehen, um diese Indexnummern in Rust-Indexnummern zu übersetzen.
Hinweis zur Effizienz
Diese Übung verwendet einen Vektor aus Vektoren, um den Inhalt von Matrizen zu speichern. Die Übung soll dir grundlegende Konzepte über Vektoren näherbringen, etwa das Indexieren und die Tatsache, dass verschachtelte Datentypen erlaubt sind. Für hochperformante Matrixalgebra und jede ähnlich effiziente Verarbeitung größerer Datenmengen ist ein Vektor aus Vektoren jedoch eine suboptimale Wahl.
Die ausführliche Erklärung dieser Ineffizienz würde den Rahmen dieser Übung und dieses Lernpfads insgesamt sprengen. Dieses Phänomen nennt man Cache-Lokalität, und wenn du mehr über die Details einer modernen Computerarchitektur erfahren möchtest, findest du über diesen Link eine gute Einführung.
