Description
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: 3
Example 2:
Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
Output: 4
Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j]
is either 0
or 1
.
Solutions
Solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def longestLine(self, mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
a = [[0] * (n + 2) for _ in range(m + 2)]
b = [[0] * (n + 2) for _ in range(m + 2)]
c = [[0] * (n + 2) for _ in range(m + 2)]
d = [[0] * (n + 2) for _ in range(m + 2)]
ans = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if mat[i - 1][j - 1]:
a[i][j] = a[i - 1][j] + 1
b[i][j] = b[i][j - 1] + 1
c[i][j] = c[i - 1][j - 1] + 1
d[i][j] = d[i - 1][j + 1] + 1
ans = max(ans, a[i][j], b[i][j], c[i][j], d[i][j])
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | class Solution {
public int longestLine(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] a = new int[m + 2][n + 2];
int[][] b = new int[m + 2][n + 2];
int[][] c = new int[m + 2][n + 2];
int[][] d = new int[m + 2][n + 2];
int ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (mat[i - 1][j - 1] == 1) {
a[i][j] = a[i - 1][j] + 1;
b[i][j] = b[i][j - 1] + 1;
c[i][j] = c[i - 1][j - 1] + 1;
d[i][j] = d[i - 1][j + 1] + 1;
ans = max(ans, a[i][j], b[i][j], c[i][j], d[i][j]);
}
}
}
return ans;
}
private int max(int... arr) {
int ans = 0;
for (int v : arr) {
ans = Math.max(ans, v);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
< |