2713.矩阵中严格递增的单元格数

链接：2713.矩阵中严格递增的单元格数
难度：Hard
标签：记忆化搜索、数组、哈希表、二分查找、动态规划、矩阵、有序集合、排序
简介：请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。

题解 1 - python

• 编辑时间：2024-06-19
• 执行用时：1089ms
• 内存消耗：71.42MB
• 编程语言：python
• 解法介绍：根据数值进行统计后dp。

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        rows = [0] * n
        cols = [0] * m
        map = defaultdict(list)
        for i in range(n):
            for j in range(m):
                map[mat[i][j]].append((i, j))
        for _, arr in sorted(map.items(), key = lambda item: item[0]):
            varr = [max(rows[i], cols[j]) + 1 for i, j in arr]
            for (i, j), v in zip(arr, varr):
                rows[i] = max(rows[i], v)
                cols[j] = max(cols[j], v)
        return max(rows)