0562：矩阵中最长的连续1线段（★）

2016-07-15 约 184 字预计阅读 1 分钟次阅读

力扣第 562 题

题目

给定一个 m x n 的二进制矩阵 mat ，返回矩阵中最长的连续1线段。

这条线段可以是水平的、垂直的、对角线的或者反对角线的。

示例 1:

输入: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
输出: 3

示例 2:

输入: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
输出: 4

提示:

m == mat.length
n == mat[i].length
1 <= m, n <= 10⁴
1 <= m * n <= 10⁴
mat[i][j] 不是 0 就是 1.

分析

对每行、每列、每个对角线递推即可。

解答

1
2
3
4
5
6
7
8
9


def longestLine(self, mat: List[List[int]]) -> int:
	def cal(A):
		return max(accumulate(A,lambda x,y:(x+1)*(y>0)))

	d, m, n = defaultdict(list), len(mat), len(mat[0])
	for i, j in product(range(m), range(n)):
		d[i+j].append(mat[i][j])
		d[i-j-m].append(mat[i][j])
	return max(cal(A) for A in chain(mat, zip(*mat), d.values()))

176 ms

目录

0562：矩阵中最长的连续1线段（★）

题目

分析

解答