LC: 562. Longest Line of Consecutive One in Matrix
https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/
562. Longest Line of Consecutive One in Matrix
Given an m x n binary matrix mat, return the length of the longest line of consecutive one in the matrix.
The line could be horizontal, vertical, diagonal, or anti-diagonal.
Example 1:
Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3Example 2:
Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
Output: 4Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j]is either0or1.
Longest Line of Consecutive One in Matrix
The Essence:
Wir sollen die Matrix nicht unnötig durchlaufen, um Länge der Linien zu bestimmen. Einige 1’s werden schon durchgelaufen. Man kann entweder die Länge der entsprechenden Linien am Anfang der Linie bestimmen oder die Länge speichern und dann in jedem Auftreten der 1 in einer Richtung inkrementieren.
Details:
Bei der ersten Methode kann ein Element darüber einfach überprüfen, ob es ein anderes Element in seiner vertikalen, horizontalen, diagonalen und antidiagonalen Richtung hat. Um Wiederholungen zu verhindern, kann jedes Element mit dem Wert 1 auch nach dem ersten Durchlauf mit einer Flagge markiert werden, um die Richtungen nicht wieder durchzusuchen. Für die zweite Methode kann die dynamische Programmierung verwendet werden, da neue Elemente die bisherigen Lösungen in 4 Richtungen optimal ergänzen. Dazu müssen die aktuellen horizontalen, vertikalen, diagonalen und antidiagonalen Längen logischerweise gespeichert werden.
Solution(s):
Default Code:
Last updated