千问 LeetCode 2713. 矩阵中严格递增的单元格数 Java实现
这是一道经典的动态规划（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: 具有该值的所有单元格坐标列表
Map<Integer, List<int[]>> 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 (List<int[]> cells : map.values()) {
// 暂存当前这一批相同数值的单元格计算出的结果
List<Integer> tempResults = new ArrayList<>();
// 第一遍遍历：计算当前批次每个单元格的最大递增长度
for (int[] cell : cells) {
int r = cell[0];
int c = cell[1];
// 当前单元格的最大长度 = 该行或该列之前的最大长度 + 1
tempResults.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 中的坐标映射以及暂存相同数值计算结果的列表。