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^5
  • 1 <= m * n <= 10^5
  • -10^5 <= mat[i][j] <= 10^5

解题思路

这是一道动态规划问题。核心思路是按值从小到大处理所有单元格，利用同行同列的历史最优解来更新当前单元格的答案。

算法思路：

  1. 排序预处理：将所有单元格按值从小到大排序，确保处理当前单元格时，所有更小值的单元格都已处理完毕。

  2. 状态定义：

    • rowMax[i]：第 i 行当前能达到的最大路径长度
    • colMax[j]：第 j 列当前能达到的最大路径长度
    • dp[i][j]：从位置 (i,j) 开始能访问的最大单元格数

  3. 状态转移：对于当前单元格 (i,j)，它可以从同行或同列中值更小的单元格转移而来：

    dp[i][j] = max(rowMax[i], colMax[j]) + 1

  4. 批量处理相同值：由于可能存在相同值的单元格，需要先收集所有相同值的单元格，计算它们的 dp 值，然后统一更新 rowMax 和 colMax 数组。

  5. 优化空间：实际实现中不需要存储完整的 dp 数组，只需要维护每行每列的最大值即可。

这种方法的优势在于避免了直接的递归搜索，通过排序保证了状态转移的正确性，时间复杂度为 O(mn log(mn))。

代码实现

class Solution {
public:
    int maxIncreasingCells(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        
        // 收集所有单元格并按值排序
        vector<array<int, 3>> cells;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cells.push_back({mat[i][j], i, j});
            }
        }
        sort(cells.begin(), cells.end());
        
        vector<int> rowMax(m, 0), colMax(n, 0);
        int ans = 0;
        
        // 按值分组处理相同值的单元格
        for (int i = 0; i < cells.size(); ) {
            int j = i;
            while (j < cells.size() && cells[j][0] == cells[i][0]) j++;
            
            // 计算当前组的dp值
            vector<int> curDp;
            for (int k = i; k < j; k++) {
                int r = cells[k][1], c = cells[k][2];
                int dp = max(rowMax[r], colMax[c]) + 1;
                curDp.push_back(dp);
                ans = max(ans, dp);
            }
            
            // 更新rowMax和colMax
            for (int k = i; k < j; k++) {
                int r = cells[k][1], c = cells[k][2];
                rowMax[r] = max(rowMax[r], curDp[k - i]);
                colMax[c] = max(colMax[c], curDp[k - i]);
            }
            
            i = j;
        }
        
        return ans;
    }
};

class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        
        # 收集所有单元格并按值排序
        cells = []
        for i in range(m):
            for j in range(n):
                cells.append((mat[i][j], i, j))
        cells.sort()
        
        row_max = [0] * m
        col_max = [0] * n
        ans = 0
        
        # 按值分组处理相同值的单元格
        i = 0
        while i < len(cells):
            j = i
            while j < len(cells) and cells[j][0] == cells[i][0]:
                j += 1
            
            # 计算当前组的dp值
            cur_dp = []
            for k in range(i, j):
                val, r, c = cells[k]
                dp = max(row_max[r], col_max[c]) + 1
                cur_dp.append(dp)
                ans = max(ans, dp)
            
            # 更新row_max和col_max
            for k in range(i, j):
                val, r, c = cells[k]
                row_max[r] = max(row_max[r], cur_dp[k - i])
                col_max[c] = max(col_max[c], cur_dp[k - i])
            
            i = j
        
        return ans

public class Solution {
    public int MaxIncreasingCells(int[][] mat) {
        int m = mat.Length, n = mat[0].Length;
        
        // 收集所有单元格并按值排序
        var cells = new List<(int val, int row, int col)>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cells.Add((mat[i][j], i, j));
            }
        }
        cells.Sort();
        
        int[] rowMax = new int[m];
        int[] colMax = new int[n];
        int ans = 0;
        
        // 按值分组处理相同值的单元格
        for (int i = 0; i < cells.Count; ) {
            int j = i;
            while (j < cells.Count && cells[j].val == cells[i].val) j++;
            
            // 计算当前组的dp值
            var curDp = new List<int>();
            for (int k = i; k < j; k++) {
                int r = cells[k].row, c = cells[k].col;
                int dp = Math.Max(rowMax[r], colMax[c]) + 1;
                curDp.Add(dp);
                ans = Math.Max(ans, dp);
            }
            
            // 更新rowMax和colMax
            for (int k = i; k < j; k++) {
                int r = cells[k].row, c = cells[k].col;
                rowMax[r] = Math.Max(rowMax[r], curDp[k - i]);
                colMax[c] = Math.Max(colMax[c], curDp[k - i]);
            }
            
            i = j;
        }
        
        return ans;
    }
}

/**
 * @param {number[][]} mat
 * @return {number}
 */
var maxIncreasingCells = function(mat) {
    const m = mat.length, n = mat[0].length;
    
    // 收集所有单元格并按值排序
    const cells = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            cells.push([mat[i][j], i, j]);
        }
    }
    cells.sort((a, b) => a[0] - b[0]);
    
    const rowMax = new Array(m).fill(0);
    const colMax = new Array(n).fill(0);
    let ans = 0;
    
    // 按值分组处理相同值的单元格
    for (let i = 0; i < cells.length; ) {
        let j = i;
        while (j < cells.length && cells[j][0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(mn log(mn))主要消耗在排序所有单元格，其中 m×n 是矩阵中的单元格总数
空间复杂度O(mn)需要存储所有单元格的信息用于排序，以及维护行列的最大值数组

相关题目