矩阵中最长的连续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数组以确保它们正确记录每行的状态?
▷🦆
题解中更新左上到右下对角线方向的最长长度时使用了表达式`cur1[j] = 1+dp1[j-1] if j>=1 else 1`,这是否意味着对于矩阵的第一列,我们无法利用前一列的数据?如果是这样,这对算法的准确性有何影响?
▷