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

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

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

思路分析

解法一：动态规划（推荐）

核心思路：

定义 dp[i][j][k] 表示以 (i, j) 结尾、方向为 k 的最长连续 1 的长度，共 4 个方向：水平（0）、垂直（1）、对角线（2）、反对角线（3）。

状态转移：若 mat[i][j] == 1，则从对应前驱位置的 dp 值 +1；否则为 0。

遍历矩阵一次，维护全局最大值。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为矩阵的行数和列数

空间复杂度：O(m × n)，dp 数组空间

class Solution {
  public int longestLine(int[][] mat) {
    if (mat == null || 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 ans = 0;

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        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;
        // 反对角线方向
        dp[i][j][3] = (i > 0 && j < n - 1 ? dp[i - 1][j + 1][3] : 0) + 1;

        for (int k = 0; k < 4; k++) {
          ans = Math.max(ans, dp[i][j][k]);
        }
      }
    }

    return ans;
  }
}

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)
    }

    ans := 0

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            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
            }

            // 反对角线方向
            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] > ans {
                    ans = dp[i][j][k]
                }
            }
        }
    }

    return ans
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	矩阵、DFS
695. 岛屿的最大面积	中等	矩阵、DFS
74. 搜索二维矩阵	中等	矩阵、二分
361. 轰炸敌人	中等	动态规划、矩阵
304. 二维区域和检索 - 矩阵不可变	中等	矩阵、前缀和
1277. 统计全为 1 的正方形子矩阵	中等	动态规划、矩阵

本文作者: HGNULB

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