562. Longest Line of Consecutive One in Matrix

1439 단어
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

Solution:


사고방식:DP 해법 dp[i][j][k]는 처음부터 숫자nums[i][j]까지 k종 상황의 연속 1의 개수를 나타낸다.k의 값은 0, 1, 2, 3으로 각각 수평, 세로, 대각선과 역대각선 등 네 가지 상황에 대응한다.dp수 그룹 업데이트 과정: 만약 숫자가 0인 경우 바로 건너뛰고 수평 방향은 앞의 dp값을 더하고 세로 방향은 위의 숫자의 dp값을 더하면 대각선 방향은 오른쪽 위의 숫자의 dp값을 더하고 역대각선은 왼쪽 위의 숫자의 dp값을 더하고 모든 값은 결과를 업데이트하는 데 사용한다.
Time Complexity: O(mn) Space Complexity: O(mn)
Solution Code:
class Solution {
    public int longestLine(int[][] M) {
        int n = M.length, max = 0;
        if (n == 0) return max;
        int m = M[0].length;
        int[][][] dp = new int[n][m][4];
        for (int i=0;i 0) dp[i][j][0] += dp[i][j-1][0]; // horizontal line
                if (j > 0 && i > 0) dp[i][j][1] += dp[i-1][j-1][1]; // anti-diagonal line
                if (i > 0) dp[i][j][2] += dp[i-1][j][2]; // vertical line
                if (j < m-1 && i > 0) dp[i][j][3] += dp[i-1][j+1][3]; // diagonal line
                max = Math.max(max, Math.max(dp[i][j][0], dp[i][j][1]));
                max = Math.max(max, Math.max(dp[i][j][2], dp[i][j][3]));
            }
        return max;
    }
}

좋은 웹페이지 즐겨찾기