LeetCode 562. 矩阵中最长的连续1线段
目录
题目描述
题意分析
给一个只含
0和1的矩阵mat，找出其中最长的一条全部由1组成的直线段，返回它的长度。直线只有四种走向：水平、垂直、主对角线（左上到右下）、反对角线（右上到左下）。线段必须是连续的，中间不能被0打断。先把「线段」这个概念的自由度数清楚：起点可以是任意格子、方向有四种、长度不定。如果按「枚举起点 × 枚举方向 × 一直走到底」去做，同一段连续的
1会被它的每个前缀重复走一遍，做了大量无用功。突破口在于换一个枚举口径：不枚举线段的起点，而是枚举线段的终点。任何一条水平线段都有唯一的最右格子，任何一条垂直线段都有唯一的最下格子——以「终点 + 方向」为标识，每条极大线段被恰好数到一次，重复彻底消失。而且这样定义后，「以
(i, j)为终点、沿某方向的连续1长度」只依赖同方向上前一个格子的同名量，天然构成一步递推。约束方面，矩阵是二维线性规模，目标显然是把每个格子只处理常数次的 $O(mn)$。四个方向互不干扰，可以在同一趟遍历里并行维护，不需要跑四遍。
边界：矩阵可能为空（行数为 0），要先挡掉再取
mat[0].length；第一行、第一列、最后一列的格子没有对应方向的前驱，这些方向要从1起算；格子为0时四个方向全部断开，长度都归零——用「跳过、保持数组默认值 0」来表达最省事。特别注意反对角线的前驱是右上方的格子(i-1, j+1)，它的列号加一，越界判断的方向和另外三个相反，是最容易写错的一处。
解法：四方向动态规划
核心思路
暴力做法是：对每个值为
1的格子，沿四个方向各自一路走到底数长度。设最长线段长度为L，则总代价是 $O(mn \cdot L)$，最坏情况（整个矩阵全是1）退化成 $O(mn \cdot \max(m, n))$。更要命的是，一条长度为L的线段被它内部的每个格子重复扫描，同样的连续性被反复确认了L遍。瓶颈就在这个重复确认上。观察一条水平线段：以
(i, j)结尾的水平连续1的长度，等于以(i, j-1)结尾的长度加一——只要(i, j)本身是1。左边那个量在遍历到(i, j)之前就已经算好了，直接取用即可，一步 $O(1)$ 就完成了原本 $O(L)$ 的扫描。四个方向各自成立同样的关系。于是定义状态：
dp[i][j][k]= 以格子(i, j)为终点、沿第k个方向的最长连续1的长度。四个方向依次编号为：0水平（前驱在左(i, j-1)）、1垂直（前驱在上(i-1, j)）、2主对角线（前驱在左上(i-1, j-1)）、3反对角线（前驱在右上(i-1, j+1)）。转移统一写成一句话：若
mat[i][j] == 1，则dp[i][j][k] = dp[前驱][k] + 1；前驱越界时视作0；若mat[i][j] == 0，则四个方向都是0。这里有个关键的正确性检查：四个方向的前驱都必须在当前格子之前被计算过。按行从上到下、每行从左到右的自然顺序遍历时，
(i, j-1)、(i-1, j)、(i-1, j-1)都在前面，没有问题；而反对角线的前驱(i-1, j+1)虽然列号更大，但行号更小，属于上一行，同样已经算完——这就是为什么四个方向可以在一趟遍历里全部搞定，不需要为反对角线单独倒着扫一遍。循环不变量：处理完
(i, j)时，所有行号小于i的格子、以及第i行中列号不大于j的格子，其四个方向的dp值都已是最终值。答案就是遍历过程中所有dp值的最大者，边算边打擂台即可。用一个
m × n × 4的三维数组存状态，最直观。由于每个格子只依赖上一行和本行左侧，其实可以压成两行的滚动数组，但矩阵规模不大时没必要，清晰度优先。
解题步骤
- 先判矩阵为空（
mat.length == 0）直接返回0。为什么：下一行就要取mat[0].length来确定列数，空矩阵会直接越界；同时空矩阵里没有任何1，答案本就是0。- 开
dp[m][n][4]三维数组，答案变量answer = 0。为什么：Java 与 Go 的数值数组默认全零，恰好等于「这个格子在这个方向上没有连续1」的语义，省掉显式初始化；answer初值取0保证全零矩阵能正确返回0。- 按行从上到下、每行从左到右双重循环。为什么：这个顺序保证四个方向的前驱格子——左、上、左上、右上——全部落在已计算区域内。右上那个前驱列号更大但行号更小，已在上一行算完，所以一趟就够。
- 遇到
mat[i][j] == 0直接continue。为什么：0会打断所有方向的连续性，四个dp值都该是0，而数组默认值本就是0，跳过即可，既表达了语义又省掉四次赋值。- 水平方向：
dp[i][j][0] = (j > 0 ? dp[i][j-1][0] : 0) + 1。为什么：接上左邻格的同方向长度再加自己这一格；j == 0时左边越界，视作长度0，于是本格从1起算——用三目表达式而不是if分支，能让「越界即 0」这条规则在四行代码里保持一致的形状。- 垂直方向：
dp[i][j][1] = (i > 0 ? dp[i-1][j][1] : 0) + 1。为什么：前驱是正上方；第一行没有上方邻居，从1起算。- 主对角线：
dp[i][j][2] = (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0) + 1。为什么：主对角线沿左上到右下延伸，前驱在左上角，行列都要非零才存在。- 反对角线：
dp[i][j][3] = (i > 0 && j + 1 < n ? dp[i-1][j+1][3] : 0) + 1。为什么：反对角线沿右上到左下延伸，前驱在右上角，所以列号的边界条件是j + 1 < n而不是j > 0——这是四个方向里唯一一个向右看的，写成j > 0是本题最高频的错误。- 用四个方向的值更新
answer。为什么：最长线段可能出现在任何格子的任何方向，必须逐一打擂台；放在格子内部更新，遍历结束就直接得到答案，不需要再扫一遍dp。- 返回
answer。以
mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]走一遍（m = 3，n = 4，答案为3）。为省篇幅只记录值为1的格子，dp四元组按[水平, 垂直, 主对角, 反对角]排列。第 0 行：
(0,1)是1，左邻(0,0)是0所以水平为0 + 1 = 1；i = 0无上方，垂直、主对角、反对角都从1起算，得[1, 1, 1, 1]，answer = 1。(0,2)是1，左邻(0,1)的水平是1，得水平2；其余三方向因i = 0均为1，得[2, 1, 1, 1]，answer = 2。第 1 行：
(1,1)是1。水平看左邻(1,0)为0，得1；垂直看上方(0,1)的垂直是1，得2；主对角看左上(0,0)，那里是0格子、dp保持默认0，得1；反对角看右上(0,2)的反对角是1，得2。四元组[1, 2, 1, 2]，answer仍是2。(1,2)是1。水平看左邻(1,1)的水平1，得2；垂直看上方(0,2)的垂直1，得2；主对角看左上(0,1)的主对角1，得2；反对角看右上(0,3)，那里是0，得1。四元组[2, 2, 2, 1]，answer仍是2。第 2 行：
(2,3)是1。水平看左邻(2,2)为0，得1；垂直看上方(1,3)为0，得1；主对角看左上(1,2)的主对角是2，得3——answer更新为3；反对角要看右上(1,4)，j + 1 = 4不小于n = 4，越界，得1。遍历结束返回
3，对应主对角线(0,1) → (1,2) → (2,3)这三个1。这里恰好体现了两处细节：(2,3)的反对角线因为在最右列而正确地从1起算（若把边界写成j > 0就会去读dp[1][4]直接越界）；而主对角线的答案是靠(1,2)那一格早就算好的2一步接出来的，完全没有沿线回扫。
代码实现
class Solution {
public int longestLine(int[][] mat) {
if (mat.length == 0) {
return 0;
}
int m = mat.length;
int n = mat[0].length;
// dp[i][j][k]：以 (i, j) 为终点、沿第 k 个方向的最长连续 1 长度。
int[][][] dp = new int[m][n][4];
int answer = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 0 打断所有方向，dp 保持默认值 0 即可。
if (mat[i][j] == 0) {
continue;
}
dp[i][j][0] = (j > 0 ? dp[i][j - 1][0] : 0) + 1;
dp[i][j][1] = (i > 0 ? dp[i - 1][j][1] : 0) + 1;
dp[i][j][2] = (i > 0 && j > 0 ? dp[i - 1][j - 1][2] : 0) + 1;
// 反对角线的前驱在右上方，边界条件是 j + 1 < n。
dp[i][j][3] = (i > 0 && j + 1 < n ? dp[i - 1][j + 1][3] : 0) + 1;
for (int k = 0; k < 4; k++) {
answer = Math.max(answer, dp[i][j][k]);
}
}
}
return answer;
}
}
func longestLine(mat [][]int) int {
if len(mat) == 0 {
return 0
}
m, n := len(mat), len(mat[0])
// dp[i][j][k]：以 (i, j) 为终点、沿第 k 个方向的最长连续 1 长度。
dp := make([][][4]int, m)
for i := range dp {
dp[i] = make([][4]int, n)
}
answer := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
// 0 打断所有方向，dp 保持默认值 0 即可。
if mat[i][j] == 0 {
continue
}
dp[i][j][0] = 1
if j > 0 {
dp[i][j][0] = dp[i][j-1][0] + 1
}
dp[i][j][1] = 1
if i > 0 {
dp[i][j][1] = dp[i-1][j][1] + 1
}
dp[i][j][2] = 1
if i > 0 && j > 0 {
dp[i][j][2] = dp[i-1][j-1][2] + 1
}
// 反对角线的前驱在右上方，边界条件是 j < n-1。
dp[i][j][3] = 1
if i > 0 && j < n-1 {
dp[i][j][3] = dp[i-1][j+1][3] + 1
}
for k := 0; k < 4; k++ {
if dp[i][j][k] > answer {
answer = dp[i][j][k]
}
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(m \cdot n)$。凭什么：双重循环恰好访问每个格子一次，格子内部是固定的四次转移加四次比较，全是常数操作；没有任何沿线回扫或重复遍历。相比暴力的 $O(mn \cdot \max(m,n))$，省下的正是「同一条线段被内部每个格子重复确认」的那部分。
- 空间复杂度：$O(m \cdot n)$。
dp数组为每个格子保存四个方向的长度，共 $4mn$ 个整数，常数因子为 4。
关键点总结
- 「找最长的某种连续结构」优先考虑以每个位置为终点来定义状态。终点唯一，所以每条极大结构只被数到一次，重复计数和重复扫描同时消失。这是 300、53、562 这一大类题的共同起手式。
- 多个方向互不干扰时，把方向做成状态的一个维度，在同一趟遍历里并行维护，而不是跑四遍。判断能否合并的标准只有一条：所有方向的前驱是否都落在同一种遍历序的「已计算区域」里。
- 遍历顺序必须由依赖关系倒推，而不是凭习惯。本题按行优先正序遍历之所以可行，是因为反对角线的前驱虽然列号更大，但行号更小、属于上一行。能主动检查这一点，是 DP 题不写出 bug 的根本。
- 用数组默认值编码「不可达 / 长度为零」的语义，遇到
0直接跳过，比写四行显式赋值更简洁也更不容易漏。- 四个方向的越界判断中，只有反对角线是向右看的（
j + 1 < n）。凡是同形代码里出现一个「反过来」的分支，都要单独在纸上画一遍再落笔。
易错点总结
- 反对角线的边界写成
j > 0并取dp[i-1][j-1]：mat = [[0,1],[1,0]]→ 反对角线与主对角线取了同一个前驱，(1,0)处算不出反对角线长度2，答案偏小。- 反对角线取
dp[i-1][j+1]却漏掉j + 1 < n判断：任何在最右列且值为1的格子 → 直接数组越界抛异常。- 遇到
0时不跳过、也不清零，直接沿用上一格的值：mat = [[1,0,1]]→(0,2)的水平长度接上了(0,1)，算出2，但中间隔着0，正确答案是1。- 遇到
0时把answer也重置：mat = [[1,1,0,1]]→ 前面已经拿到的2被清掉，最终返回1。答案是全局最大值，绝不能随局部状态回退。dp值不加+1：mat = [[1]]→ 所有方向都是0，返回0，正确答案是1。当前格子自身必须计入长度。- 没有判空就取
mat[0].length：mat = []→ 数组越界；正确行为是返回0。answer只在某一个方向上更新（比如只看水平）：mat = [[1],[1],[1]]→ 水平长度恒为1，返回1，而垂直方向的3被完全忽略。- 状态定义成「以
(i, j)为起点」却仍按正序遍历：起点定义要求先知道右下方的结果 → 依赖方向与遍历方向相反，读到的全是初值0，所有长度都变成1。- 用一个二维
dp存四个方向的最大值而不是分开存：mat中某格水平长3、垂直长1→ 下一格垂直方向误接了3，长度凭空变长，答案偏大。四个方向必须各自独立地递推。- 对每个
1沿四个方向回扫求长度：全1的 $200 \times 200$ 矩阵 → 复杂度 $O(mn \cdot \max(m,n))$，规模再大一档就超时，且大量重复确认同一段连续性。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 221. 最大正方形 | 中等 | 同为「以右下角为终点」的矩阵 DP，但转移取三个方向的最小值而非各自独立 |
| 1277. 统计全为 1 的正方形子矩阵 | 中等 | 状态与 221 完全相同，但答案是所有 dp 值求和而非取最大 |
| 85. 最大矩形 | 困难 | 目标是任意长宽的矩形，需逐行压成柱状图再用单调栈，DP 递推不再够用 |
| 485. 最大连续 1 的个数 | 简单 | 本题水平方向的一维退化版，一个计数器即可，可当作理解「以终点计数」的入门 |
| 487. 最大连续1的个数 II | 中等 | 允许翻转一个 0，状态需增加「已用几次翻转」这一维 |
| 1004. 最大连续1的个数 III | 中等 | 允许翻转 k 个 0，转为滑动窗口维护「窗口内 0 的个数不超过 k」 |
| 329. 矩阵中的最长递增路径 | 困难 | 路径可任意拐弯，依赖关系无固定遍历序，只能用记忆化搜索而非递推 |
| 931. 下降路径最小和 | 中等 | 同为逐行递推，但每格从上一行三个相邻列中取最优，路径允许左右摆动 |