摘要
Title: 2713. 矩阵中严格递增的单元格数
Tag: dp
Memory Limit: 64 MB
Time Limit: 1000 ms

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

题意

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为起始单元格。

从起始单元格出发，你可以移动到同一行或同一列中的任何其他单元格，但前提是目标单元格的值严格大于当前单元格的值。

你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的单元格的最大数量。

返回一个表示可访问单元格最大数量的整数。

思路

首先是考虑，针对于某一行或者某一列来说，顺序是无关紧要的，所以可以对坐标对应的值进行桶排，并进行 sort ，这样一定是从数值小的到数值大的开始遍历。也就是说我们可以得到最简单的一个dp表达式，就是 dp[i][j] = max(max(dp[i][j'] + 1), max(dp[i'][j] + 1)) 其中 mat[i][j'] < mat[i][j] mat[i'][j] < mat[i][j]
其次，比如值为 2 的被遍历了，它的其中一个坐标是 (1, 1)，那么我只关心第一行的目前dp最大值是多少，第一列的dp最大值是多少，这两个取个最大值并+1，就是我的dp值。所以需要两个数组，行数组和列数组维护各自行列的dp最大值

代码

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])

        row = [0] * m
        col = [0] * n

        g = defaultdict(list)
        for i in range(m):
            for j in range(n):
                g[mat[i][j]].append((i, j))
        g = sorted(g.items(), key=lambda k: k[0])
        for val, pos_lst in g:
            res = [max(row[i], col[j]) + 1 for i, j in pos_lst]
            for (x, y), d in zip(pos_lst, res):
                row[x] = max(row[x], d)
                col[y] = max(col[y], d)
        return max(row)