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

难度: Hard

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

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

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

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

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

示例 1：

输入：mat = [[3,1],[3,4]]
输出：2
解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。

示例 2：

输入：mat = [[1,1],[1,1]]
输出：1
解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。

示例 3：

输入：mat = [[3,1,6],[-9,5,7]]
输出：4
解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
-10⁵ <= mat[i][j] <= 10⁵

Submission

运行时间: 704 ms

内存: 54.7 MB

class Solution:
    def maxIncreasingCells(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = [[0 for _ in range(n)] for _ in range(m)]
        res = []
        for i in range(m):
            for j in range(n):
                res.append((grid[i][j],i,j))
        res.sort(key = lambda c:c[0])
        rowMax = [0] * m
        colMax = [0] * n
        pre = res[0][0]
        cache = []
        for v,x,y in res:
            if v > pre:
                pre = v
                # 先更新Max
                for cache_v,cache_x,cache_y in cache:
                    rowMax[cache_x] = max(rowMax[cache_x],cache_v)
                    colMax[cache_y] = max(colMax[cache_y],cache_v)
                cache = []
            ans[x][y] = max(rowMax[x] , colMax[y]) + 1
            cache.append((ans[x][y] ,x,y))
        return max(ans[i][j] for i in range(m) for j in range(n)) 
        # @cache
        # def dfs(i: int, j: int) -> int:
        #     res = 0
        #     for x in range(m):
        #         if x!= i and grid[x][j] > grid[i][j]:
        #             res = max(res,dfs(x, j))
        #     for y in range(n):
        #         if y!= j and grid[i][y] > grid[i][j]:
        #             res = max(res,dfs(i, y))
        #     return res +1
        # return max(dfs(i, j) for i in range(m) for j in range(n))

Explain

题解使用了动态规划和排序的方法来解决问题。首先，将矩阵中的所有单元格与它们的坐标一起存储到列表中，并按照单元格的值进行排序。接着，定义两个数组 rowMax 和 colMax 来存储每行和每列的最大可访问单元格数。通过遍历排序后的单元格列表，利用动态规划的思想，计算从每个单元格开始可以访问的最大单元格数量。如果当前单元格的值与前一个不同，则更新 rowMax 和 colMax。对于每个单元格，其可访问数是其所在行和列的最大可访问数中的最大值加一。最后，返回所有单元格的最大可访问数。

时间复杂度: O(mn log(mn))

空间复杂度: O(mn)

class Solution:
    def maxIncreasingCells(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = [[0 for _ in range(n)] for _ in range(m)]
        res = []
        for i in range(m):
            for j in range(n):
                res.append((grid[i][j],i,j))
        res.sort(key = lambda c:c[0])
        rowMax = [0] * m
        colMax = [0] * n
        pre = res[0][0]
        cache = []
        for v,x,y in res:
            if v > pre:
                pre = v
                for cache_v,cache_x,cache_y in cache:
                    rowMax[cache_x] = max(rowMax[cache_x],cache_v)
                    colMax[cache_y] = max(colMax[cache_y],cache_v)
                cache = []
            ans[x][y] = max(rowMax[x] , colMax[y]) + 1
            cache.append((ans[x][y] ,x,y))
        return max(ans[i][j] for i in range(m) for j in range(n))

Explore

在这个题解中，将所有单元格按它们的值进行排序是为了确保在处理每一个单元格时，我们已经考虑了所有小于当前单元格值的单元格。这样的排序保证了在动态规划的过程中，我们从最小的值开始，向上扩展到更大的值，这是确保每个单元格被正确考虑在内，并计算出以该单元格为起点的最长递增路径的关键。通过这种方式，可以简化状态转移的复杂度，因为我们总是在已经处理过并存储了最优结果的单元格上进行构建。

在这个问题中，动态规划用于计算每个单元格作为起点的最长递增路径的长度。状态转移方程是通过比较当前单元格的最大可能递增路径与其所在行和列已知的最大路径长度。具体来说，对于每个单元格 (x, y)，其最大递增路径为 `ans[x][y] = max(rowMax[x], colMax[y]) + 1`。这里，`rowMax[x]` 和 `colMax[y]` 分别表示在行x和列y中，截至当前单元格之前能达到的最大递增路径的长度。通过这种方式，我们可以确保利用已经计算过的信息来更新当前单元格的最大路径长度。

更新 `rowMax` 和 `colMax` 数组的过程中，这两个数组分别记录了当前行和列中所有已处理单元格的最大递增路径长度。当处理一个新的值时（即当前单元格的值与前一个单元格的值不同时），我们会遍历 `cache` 列表中暂存的单元格信息，这个列表包含了具有相同值的所有单元格的最大路径以及它们的坐标。通过这样的更新，我们确保在转移到新的单元格值时，已经充分利用了之前计算的结果，从而不会遗漏任何可能的递增路径。

在题解的实现中，`cache` 列表用于暂时存储在处理具有相同值的单元格群时计算得到的最大递增路径长度及其坐标。只有当我们在遍历过程中遇到一个新的单元格值时（即当前单元格的值大于前一个处理的单元格的值），我们才清空 `cache` 列表，并将其值更新到 `rowMax` 和 `colMax` 数组。这个更新是必要的，因为它标志着我们已经完成了对当前值所有单元格的处理，并且可以安全地更新行和列的最大值，为处理下一个更大值的单元格做准备。