题目描述

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

算法1

(暴力枚举) $O(m*n)$

暴搜矩阵每个点，update连续最长1的长度

时间复杂度

O（m*n）
O（1）

参考文献

C++ 代码

class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        if(M.size()==0 ||M[0].size()==0) return 0;
        int m=M.size(), n=M[0].size(), res=0;
        vector<vector<int>> dirs{{-1,0},{0,-1},{-1,-1},{-1,1}};//当前位置的左方上方
        for(int i=0 ;i<m; i++)
            for(int j=0;j<n;j++)
            {
                if(M[i][j]==0) continue;
                for(auto dir:dirs)
                {
                    int cnt=0, x=i, y=j;
                    while(x>=0 && x<m && y>=0 && y<n && M[x][y]==1)
                    {
                        x+=dir[0], y+=dir[1];
                        ++cnt;
                    }                    
                    res=max(res, cnt);
                }
            }
        return res;
    }
};

算法2

(DP) $O(m*n)$

dp[i][j][0]表示到grid[i][j]水平连续1的长度，dp[i][j][1]表示到grid[i][j]垂直连续1的长度，dp[i][j][3]表示到grid[i][j]对角线连续1的长度，dp[i][j][3]表示到grid[i][j]反对角线连续1的长度。

时间复杂度

time O(mn)
space O(mn)

参考文献

C++ 代码

class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        int H = M.size(), W = H?M[0].size():0, res = 0;
        vector<vector<vector<int>>> dp(H, vector<vector<int>>(W, vector<int>(4, 0)));
        for(int i=0;i<H;i++) 
            for(int j=0;j<W;j++)
                if(M[i][j]==1) {
                    res=max(res,  dp[i][j][0]= 1 + (j?dp[i][j-1][0]:0)  ); // horizontal
                    res=max(res,  dp[i][j][1]= 1 + (i?dp[i-1][j][1]:0)  ); // vertical
                    res=max(res,  dp[i][j][2]= 1 + (i&&j?dp[i-1][j-1][2]:0)  ); // diagonal
                    res=max(res,  dp[i][j][3]= 1 + (i&&j<W-1?dp[i-1][j+1][3]:0)  ); // anti-diagonal
                }
        return res;
    }
};