562.
1. Question
Given a 01 matrix M , find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.
Example:
Input:
[[0,1,1,0],
[0,1,1,0],
[0,0,0,1]]
Output:
3
Hint:The number of elements in the given matrix will not exceed 10,000.
2. Implementation
(1) DP
思路: 建立一个 m * n * 4的3维数组,
dp[i][j][0]表示在(i, j) 水平方向上最长的连续1的个数
dp[i][j][1]表示在(i, j) 垂直方向上最长的连续1的个数
dp[i][j][2]表示在(i, j) 正对角线上最长的连续1的个数
dp[i][j][3]表示在(i, j) 反对角线上最长的连续1的个数
class Solution {
public int longestLine(int[][] M) {
if (M == null || M.length == 0) {
return 0;
}
int m = M.length, n = M[0].length;
int[][][] dp = new int[m][n][4];
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] == 1) {
dp[i][j][0] = j > 0 ? dp[i][j - 1][0] + 1 : 1;
dp[i][j][1] = i > 0 ? dp[i - 1][j][1] + 1 : 1;
dp[i][j][2] = i > 0 && j > 0 ? dp[i - 1][j - 1][2] + 1 : 1;
dp[i][j][3] = i > 0 && j < n - 1 ? dp[i - 1][j + 1][3] + 1 : 1;
res = Math.max(res, Math.max(dp[i][j][0], dp[i][j][1]));
res = Math.max(res, Math.max(dp[i][j][2], dp[i][j][3]));
}
}
}
return res;
}
}
3. Time & Space Complexity
DP: 时间复杂度O(mn), 空间复杂度O(mn)