这是一道经典的动态规划DP结合排序的题目。题目核心思路题目要求从任意单元格出发每次只能移动到同一行或同一列中值严格大于当前单元格的格子求能访问的最大单元格数量。1. 动态规划状态定义我们可以定义 dp[i][j] 为以 (i, j) 单元格作为路径终点时能访问的最大单元格数量。状态转移方程为dp[i][j] max(第i行的最大路径长度, 第j列的最大路径长度) 1。2. 排序保证严格递增为了保证转移的正确性即从小值转移到大值我们需要将矩阵中的所有单元格按照数值从小到大进行排序。这样在遍历时当前处理的单元格一定是由之前数值更小的单元格转移而来的。3. 空间优化我们不需要维护完整的二维 dp 数组。只需要维护两个一维数组* rowMax[i]记录第 i 行目前能达到的最大路径长度。* colMax[j]记录第 j 列目前能达到的最大路径长度。4. 处理相同数值的细节关键点题目要求“严格递增”因此数值相同的单元格之间不能互相转移。如果我们在遍历同一批相同数值的单元格时算出一个结果就立刻更新 rowMax 和 colMax会导致同批次的其他单元格错误地利用这个更新后的值。解决方法对于相同数值的所有单元格先统一计算出它们的结果并暂存起来等这一批全部算完后再统一去更新 rowMax 和 colMax。Java 实现代码import java.util.*;class Solution {public int maxIncreasingCells(int[][] mat) {int m mat.length;int n mat[0].length;// 1. 使用 TreeMap 将矩阵中的值按从小到大排序并存储对应的坐标// Key: 单元格的值, Value: 具有该值的所有单元格坐标列表MapInteger, Listint[] map new TreeMap();for (int i 0; i m; i) {for (int j 0; j n; j) {map.computeIfAbsent(mat[i][j], k - new ArrayList()).add(new int[]{i, j});}}// rowMax[i] 表示第 i 行目前能达到的最大递增单元格数int[] rowMax new int[m];// colMax[j] 表示第 j 列目前能达到的最大递增单元格数int[] colMax new int[n];int result 0;// 2. 按值从小到大遍历for (Listint[] cells : map.values()) {// 暂存当前这一批相同数值的单元格计算出的结果ListInteger tempResults new ArrayList();// 第一遍遍历计算当前批次每个单元格的最大递增长度for (int[] cell : cells) {int r cell[0];int c cell[1];// 当前单元格的最大长度 该行或该列之前的最大长度 1tempResults.add(Math.max(rowMax[r], colMax[c]) 1);}// 第二遍遍历统一更新 rowMax 和 colMax防止同值单元格互相影响for (int i 0; i cells.size(); i) {int r cells.get(i)[0];int c cells.get(i)[1];int currentMax tempResults.get(i);rowMax[r] Math.max(rowMax[r], currentMax);colMax[c] Math.max(colMax[c], currentMax);// 更新全局最大值result Math.max(result, currentMax);}}return result;}}复杂度分析* 时间复杂度O(mn log(mn))。其中 m 和 n 是矩阵的行数和列数。主要耗时在将所有 m*n 个元素放入 TreeMap或排序的过程中。后续的双层遍历总次数也是 m*n。* 空间复杂度O(mn)。主要用于存储 TreeMap 中的坐标映射以及暂存相同数值计算结果的列表。
