• ㊗️
• 大家
• offer
• 多多！

## Problem

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 <= 10^4$
• $1 <= m * n <= 10^4$
• mat[i][j] is either 0 or 1.

## Code

class Solution {
public int longestLine(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int max = 0;

for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j++) {
if(mat[i][j] == 0) continue;

int curRow = 0, curCol = 0, diag = 0, anti = 0;

if (j == 0 || mat[i][j - 1] == 0) {
int col = j;

while (col < n && mat[i][col] == 1) {
curRow++;
col++;
}

max = Math.max(max, curRow);
}

if (i == 0 || mat[i - 1][j] == 0) {
int row = i;

while (row < m && mat[row][j] == 1) {
curCol++;
row++;
}

max = Math.max(max, curCol);
}

if (i == 0 || j == 0 || mat[i - 1][j - 1] == 0) {
int row = i;
int col = j;

while (row < m && col < n && mat[row][col] == 1) {
diag++;
row++;
col++;
}

max = Math.max(max, diag);
}

if (i == 0 || j == n - 1 || mat[i - 1][j + 1] == 0) {
int row = i;
int col = j;

while (row < m && col >= 0 && mat[row][col] == 1) {
anti++;
row++;
col--;
}

max = Math.max(max, anti);
}
}
}

return max;
}
}

class Solution {
public int longestLine(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int max = 0;

int[][][] dp = new int[m][n][4];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) continue;

for (int k = 0; k < 4; k++) {
dp[i][j][k] = 1;
}

// 行
if (j > 0) {
dp[i][j][0] += dp[i][j - 1][0];
}

// 列
if (i > 0) {
dp[i][j][1] += dp[i - 1][j][1];
}

// 对角线
if (i > 0 && j > 0 ) {
dp[i][j][2] += dp[i - 1][j - 1][2];
}

// 反对角线
if (i > 0 && j < n - 1) {
dp[i][j][3] += dp[i - 1][j + 1][3];
}

int max1 = Math.max(dp[i][j][0], dp[i][j][1]);
int max2 = Math.max(dp[i][j][2], dp[i][j][3]);
max = Math.max(max, Math.max(max1, max2));
}
}

return max;
}
}

class Solution {
public int longestLine(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int max = 0;

int[][] dp = new int[n][4];

for (int i = 0; i < m; i++) {
int prevDiag = 0; // dp[i - 1][j - 1][2];

for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
dp[j][0] = j > 0 ? dp[j - 1][0] + 1 : 1;
dp[j][1] = i > 0 ? dp[j][1] + 1 : 1;

int prev = dp[j][2];

dp[j][2] = (i > 0 && j > 0) ? prevDiag + 1 : 1;

prevDiag = prev;

dp[j][3] = (i > 0 && j < n - 1) ? dp[j + 1][3] + 1 : 1;

int max1 = Math.max(dp[j][0], dp[j][1]);
int max2 = Math.max(dp[j][2], dp[j][3]);
max = Math.max(max, Math.max(max1, max2));
} else {
prevDiag = dp[j][2];
dp[j][0] = dp[j][1] = dp[j][2] = dp[j][3] = 0;
}
}
}

return max;
}
}