首页 > 代码库 > 562. Longest Line of Consecutive One in Matrix

562. Longest Line of Consecutive One in Matrix

This is an easy question.  No matter what kind of method you chose, the time complexity is at least O(m*n), becasue you have to traverse each element at least once. Here, we have a straight forward method without any maps... 

class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        if (M.empty()) return 0;
        int result = 0;
        int cur = 0;
        for (int i = 0; i < M.size(); i++) {
            cur = 0;
            for (int j = 0; j < M[i].size(); j++) {
                if (M[i][j]) cur++;
                else cur = 0;
                result = max(result, cur);
            }
        }
        for (int j = 0; j < M[0].size(); j++) {
            cur = 0;
            for (int i = 0; i < M.size(); i++) {
                if (M[i][j]) cur++;
                else cur = 0;
                result = max(result, cur);
            }
        }
        
        //int my = M.size(), mx = M[0].size();
        for (int j = -(int)M.size(); j < (int)M[0].size(); j++) {
            cur = 0;
            for (int i = 0; i < M.size(); i++) {
                if (j + i < 0 || i + j >= M[0].size()) continue;
                else {
                    if (M[i][j + i]) cur++;
                    else cur = 0;
                    result = max(result, cur);
                }
            }
        }
        for (int j = 0; j < M[0].size() + M.size(); j++) {
            cur = 0;
            for (int i = 0; i < M.size(); i++) {
                if (j - i < 0 || j - i >= M[0].size()) continue;
                else {
                    if (M[i][j - i]) cur++;
                    else cur = 0;
                    result = max(result, cur);
                }
            }
        }
        return result;
    }
};

Pay attention to the third for-loop. Because the return value of size() is size_type, an unsigned value, when you make some operations with int, be very careful about bugs, especially when the value is minus.

562. Longest Line of Consecutive One in Matrix