leetcode
leetcode 501 ~ 550
矩阵中最长的连续1线段

矩阵中最长的连续1线段

难度:

标签:

题目描述

代码结果

运行时间: 85 ms, 内存: 17.5 MB


/*
 题目思路:
 使用Java Stream API处理二维矩阵找出矩阵中最长的连续1线段。
 Java Stream API更适合处理集合数据而不是二维数组,所以这里展示的是一种将二维数组转换为一维Stream来处理的方法。
 最后我们会合并不同方向的检查结果来获得最终的最大值。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
 
public class Solution {
    public int longestLine(int[][] M) {
        if (M == null || M.length == 0) return 0;
        int rows = M.length, cols = M[0].length;
        int max = 0;
 
        // 水平
        for (int[] row : M) {
            max = Math.max(max, findMaxConsecutiveOnes(row));
        }
 
        // 垂直
        for (int j = 0; j < cols; j++) {
            final int colIdx = j;
            max = Math.max(max, findMaxConsecutiveOnes(IntStream.range(0, rows).map(i -> M[i][colIdx]).toArray()));
        }
 
        // 对角线和反对角线
        for (int k = 0; k < rows + cols - 1; k++) {
            final int diagIdx = k;
            max = Math.max(max, findMaxConsecutiveOnes(IntStream.range(0, rows).map(i -> (diagIdx - i >= 0 && diagIdx - i < cols) ? M[i][diagIdx - i] : 0).toArray()));
            max = Math.max(max, findMaxConsecutiveOnes(IntStream.range(0, rows).map(i -> (diagIdx - i >= 0 && diagIdx - i < cols) ? M[rows - 1 - i][diagIdx - i] : 0).toArray()));
        }
 
        return max;
    }
 
    private int findMaxConsecutiveOnes(int[] arr) {
        return Arrays.stream(arr).boxed().collect(Collectors.toList()).stream()
                .map(a -> a == 1 ? a : 0)
                .collect(Collectors.reducing(0, Integer::sum));
    }
}

解释

方法:

这个题解采用动态规划的思路来解决问题。对于每个位置上的1,我们考虑以它为结尾的4个方向上最长的连续1线段:水平、垂直、左上到右下对角线和右上到左下对角线。我们用三个DP数组 dp0, dp1, dp2 分别记录前三个方向的最长长度。对于垂直方向,我们直接用一个单独的数组 cur 来记录以当前列为结尾的最长长度。最后,我们取这4个方向的最大值作为答案。

时间复杂度:

O(mn)

空间复杂度:

O(m+n)

代码细节讲解

🦆
在解法中提到使用了三个DP数组(dp0, dp1, dp2)来分别记录三个不同方向的最长连续1线段长度,但如何初始化这些DP数组以确保它们正确记录每行的状态?
这些DP数组(dp0, dp1, dp2)都是在每一行开始时通过复制当前行的矩阵状态来初始化的。这意味着它们的初始状态直接反映了当前行中的1的位置(以1为起始长度,0则保持0)。这种初始化方法确保了每次迭代时,DP数组都能够从当前行的实际情况开始计算,逐步构建起从上一行继承的连续1的长度。因此,每次移动到新的一行时,我们实际上是在重置DP状态,以便在新行的上下文中重新计算连续的1的长度。
🦆
题解中更新左上到右下对角线方向的最长长度时使用了表达式`cur1[j] = 1+dp1[j-1] if j>=1 else 1`,这是否意味着对于矩阵的第一列,我们无法利用前一列的数据?如果是这样,这对算法的准确性有何影响?
是的,对于矩阵的第一列而言,由于没有左上角的元素,我们无法从前一列继承连续的1的长度,因此在第一列的计算中始终设置为1(如果当前位置为1)。这不会影响算法的准确性,因为对角线在矩阵的边界处本就开始或结束,而我们的处理确保了在这些边界情况下的正确性和完整性。
🦆
在处理右上到左下对角线的更新时,表达式`cur2[j] = 1+dp2[j+1] if j
在代码中,`cur2[j] = 1+dp2[j+1] if j
🦆
为什么在计算垂直方向最长连续1线段的长度时,选择单独使用一个数组`cur`而不是将其包含在DP数组中?
在计算垂直方向的最长连续1线段长度时,使用单独的数组`cur`是为了简化问题的处理。垂直方向的连续1的计算只依赖于当前元素的上一个元素,因此可以使用单行的数组来追踪每列的连续1的长度。与DP数组相比,这种方法减少了内存使用,并且简化了更新逻辑,因为每次只需要考虑当前元素和它正上方的元素。如果将垂直方向的计算也整合进DP数组,虽然可行,但会增加处理的复杂性,并可能不如当前方法直观。

相关问题