矩阵中最长的连续1线段

难度: Medium

Submission

运行时间: 85 ms

内存: 17.5 MB

class Solution:
    def longestLine(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        dp0, dp1, dp2 = mat[0][:], mat[0][:], mat[0][:]
        ans = max(mat[0])

        for i in range(1, m):
            cur0, cur1, cur2 = mat[i][:], mat[i][:], mat[i][:]
            for j in range(n):
                if mat[i][j]==0:
                    continue
                cur0[j] = 1+dp0[j]
                cur1[j] = 1+dp1[j-1] if j>=1 else 1
                cur2[j] = 1+dp2[j+1] if j<n-1 else 1
            dp0, dp1, dp2 = cur0[:], cur1[:], cur2[:]
            #print(i, dp0)
            ans = max(ans, max(dp0), max(dp1),max(dp2))
        
        cur = [0]*m
        for j in range(n):
            for i in range(m):
                if mat[i][j]==0:
                    cur[i] = 0
                else:
                    cur[i] += 1
            #print(j, cur)
            ans = max(ans, max(cur))
        
        return ans

Explain

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

时间复杂度: O(mn)

空间复杂度: O(m+n)

class Solution:
    def longestLine(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        # 初始化三个DP数组，分别表示水平、左上到右下对角线、右上到左下对角线方向的最长长度
        dp0, dp1, dp2 = mat[0][:], mat[0][:], mat[0][:]
        ans = max(mat[0])

        for i in range(1, m):
            cur0, cur1, cur2 = mat[i][:], mat[i][:], mat[i][:]
            for j in range(n):
                if mat[i][j]==0:
                    continue
                # 更新水平方向的最长长度
                cur0[j] = 1+dp0[j]
                # 更新左上到右下对角线方向的最长长度
                cur1[j] = 1+dp1[j-1] if j>=1 else 1
                # 更新右上到左下对角线方向的最长长度
                cur2[j] = 1+dp2[j+1] if j<n-1 else 1
            dp0, dp1, dp2 = cur0[:], cur1[:], cur2[:]
            ans = max(ans, max(dp0), max(dp1),max(dp2))
        
        # 计算垂直方向的最长长度
        cur = [0]*m
        for j in range(n):
            for i in range(m):
                if mat[i][j]==0:
                    cur[i] = 0
                else:
                    cur[i] += 1
            ans = max(ans, max(cur))
        
        return ans

Explore

这些DP数组(dp0, dp1, dp2)都是在每一行开始时通过复制当前行的矩阵状态来初始化的。这意味着它们的初始状态直接反映了当前行中的1的位置（以1为起始长度，0则保持0）。这种初始化方法确保了每次迭代时，DP数组都能够从当前行的实际情况开始计算，逐步构建起从上一行继承的连续1的长度。因此，每次移动到新的一行时，我们实际上是在重置DP状态，以便在新行的上下文中重新计算连续的1的长度。

是的，对于矩阵的第一列而言，由于没有左上角的元素，我们无法从前一列继承连续的1的长度，因此在第一列的计算中始终设置为1（如果当前位置为1）。这不会影响算法的准确性，因为对角线在矩阵的边界处本就开始或结束，而我们的处理确保了在这些边界情况下的正确性和完整性。

在代码中，`cur2[j] = 1+dp2[j+1] if j<n-1 else 1`的条件`j<n-1`确保了只有当`j+1`仍然在数组的合法索引范围内时，我们才会访问`dp2[j+1]`。这样的条件检查防止了数组越界的错误。当`j`等于`n-1`（即最后一列）时，对角线不能向右延伸，因此直接将其置为1（如果当前位置为1），这符合对角线的起始逻辑。

在计算垂直方向的最长连续1线段长度时，使用单独的数组`cur`是为了简化问题的处理。垂直方向的连续1的计算只依赖于当前元素的上一个元素，因此可以使用单行的数组来追踪每列的连续1的长度。与DP数组相比，这种方法减少了内存使用，并且简化了更新逻辑，因为每次只需要考虑当前元素和它正上方的元素。如果将垂直方向的计算也整合进DP数组，虽然可行，但会增加处理的复杂性，并可能不如当前方法直观。