文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個01矩陣 M，找到矩陣中最長的連續(xù)1線段。
這條線段可以是水平的、垂直的、對角線的或者反對角線的。

示例: 輸入: [[0,1,1,0],[0,1,1,0],[0,0,0,1]] 輸出: 3 提示: 給定矩陣中的元素數(shù)量不會超過 10,000。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-line-of-consecutive-one-in-matrix
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 建立四個方向的DP數(shù)組即可，求各方向的前綴和，遇到0從新開始累計

class Solution { public:int longestLine(vector<vector<int>>& M) {if(M.empty() || M[0].empty())return 0;int m = M.size(), n = M[0].size(), i, j;vector<vector<int>> h(m,vector<int>(n,0)),v(m,vector<int>(n,0)), p_45(m,vector<int>(n,0)),n_45(m,vector<int>(n,0));int maxlen = 0;for(i = 0; i < m; i++) {for(j = 0; j < n; j++){if(M[i][j] == 0)continue;h[i][j] = i-1>=0 ? h[i-1][j]+1 : 1;v[i][j] = j-1>=0 ? v[i][j-1]+1 : 1;p_45[i][j] = (i>0 && j+1 <n) ? p_45[i-1][j+1]+1 : 1;n_45[i][j] = (i>0 && j>0) ? n_45[i-1][j-1]+1 : 1;maxlen = max(maxlen,h[i][j]);maxlen = max(maxlen,v[i][j]);maxlen = max(maxlen,p_45[i][j]);maxlen = max(maxlen,n_45[i][j]);}}return maxlen;} };

120 ms 28.3 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 562. 矩阵中最长的连续1线段（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。