LeetCode 562. 矩阵中最长的连续1线段

2020-07-08 HGNULB 约 5 分钟

文章信息 7 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决会员题 1-2 猿辅导

题目描述

✅ 562. 矩阵中最长的连续1线段

题意分析

在零一矩阵中找全部由一组成的最长直线段，返回其中格子的数量。线段可以水平、垂直、沿主对角线或反对角线，但不能跨过零或中途转弯。

一条线段以当前格结尾时，去掉当前格，剩余部分就以同方向的前一格结尾。于是可以复用前驱的连续长度，为每个格子分别维护四个方向的状态。

解法：四方向动态规划

核心思路

[!blue]
为每个终点分别记录四个方向的连续长度。 dp[i][j][k] 表示以 (i,j) 为终点、方向为 k 的最长连续一线段长度。方向 0、1、2、3 的前驱依次为左边、上边、左上、右上，并且都只读取前驱的同方向状态。

当前格为一时，若前驱存在，就在其记录上加一；前驱越界或为零时，其可延续长度为零，当前格自己构成长度一。当前格为零时，任何连续一线段都不能在这里结尾，四个状态保持默认零。

固定终点和方向后，前驱位置唯一。合法线段要么只有当前格，要么由前驱的合法线段延长而来，因此这条转移同时覆盖全部可能，也不会拼出转弯或跨零的线段。方向不能合并成一个最大值，否则下一步可能接上来自另一方向的长度。

按行从上到下、行内从左到右计算，左前驱已经在本行处理完，其余三个都属于上一行；右上虽然列号更大，也已经算好。每个状态都用来更新 answer，而任意合法线段都有终点，所以最终得到全矩阵的最大长度。

解题步骤

建立每格四方向的长度表。

按行扫描，零格保持默认零。

一格分别读取存在的前驱并加一。

用四个长度更新全局最大值。

代码实现

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(mn)$，每格固定四次转移。

空间复杂度：$O(mn)$，每格保存四个长度。

关键点总结

[!green]

状态绑定终点和方向。

右上前驱位于上一行，不需要单独反向扫描。

零只中断局部长度，不清空已经得到的全局答案。

易错点总结

[!yellow]

反对角线也读取左上：漏掉右上到左下的线段。

右上访问不检查最右列：会越界。

一个值保存四方向最大长度：不同方向的状态会错误连接。

零格仍沿用邻格长度：跨过零连接成不连续线段。

全零矩阵的答案保持零；孤立的一在四个方向上都得到长度一。零只清断当前方向的连续长度，不能重置全局 answer。

相似题目

题目	难度	关联与区别
485. 最大连续 1 的个数	简单	一维连续1计数是基础，本题对水平、竖直和两条对角方向分别维护延续长度。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2020/66378510

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！