562. Longest Line of Consecutive One in Matrix

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• 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;
    }
}