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
原文：http://www.cnblogs.com/tekkaman-blade/p/6936081.html