这道题的 C 实现思路和 Java 版本完全一致都是采用动态规划DP结合排序的方法。在 C 中我们可以利用 std::map 自动按键值单元格的值排序的特性来优雅地替代 Java 中的 TreeMap。C 实现代码#include vector#include map#include algorithmusing namespace std;class Solution {public:int maxIncreasingCells(vectorvectorint mat) {int m mat.size();int n mat[0].size();// 1. 使用 map 将矩阵中的值按从小到大排序并存储对应的坐标// Key: 单元格的值, Value: 具有该值的所有单元格坐标列表mapint, vectorpairint, int valueMap;for (int i 0; i m; i) {for (int j 0; j n; j) {valueMap[mat[i][j]].emplace_back(i, j);}}// rowMax[i] 表示第 i 行目前能达到的最大递增单元格数vectorint rowMax(m, 0);// colMax[j] 表示第 j 列目前能达到的最大递增单元格数vectorint colMax(n, 0);int result 0;// 2. 按值从小到大遍历 mapfor (auto [val, cells] : valueMap) {// 暂存当前这一批相同数值的单元格计算出的结果// 这一步是为了防止同值单元格之间互相影响题目要求严格递增vectorint tempResults;// 第一遍遍历计算当前批次每个单元格的最大递增长度for (auto [r, c] : cells) {// 当前单元格的最大长度 该行或该列之前的最大长度 1tempResults.push_back(max(rowMax[r], colMax[c]) 1);}// 第二遍遍历统一更新 rowMax 和 colMaxfor (int i 0; i cells.size(); i) {int r cells[i].first;int c cells[i].second;int currentMax tempResults[i];rowMax[r] max(rowMax[r], currentMax);colMax[c] max(colMax[c], currentMax);// 更新全局最大值result max(result, currentMax);}}return result;}};核心思路与复杂度解析1. 排序保证转移顺序利用 std::map 自动按 key单元格的值从小到大排序的特性保证了我们在计算当前单元格的递增长度时只能从数值更小的单元格转移过来完美契合题目“严格递增”的要求。2. 空间优化与同值处理* 我们只维护两个一维数组 rowMax 和 colMax分别记录每一行和每一列目前能达到的最大递增长度。* 关键细节对于数值相同的多个单元格它们之间不能互相转移。因此代码中采用了“先批量计算后批量更新”的策略使用 tempResults 暂存结果避免了同批次内的单元格互相干扰。3. 复杂度分析* 时间复杂度O(mn log(mn))。主要耗时在将所有 m*n 个元素插入 map 进行排序。后续的遍历总次数也是 m*n。* 空间复杂度O(mn)。主要用于 map 存储所有坐标以及 tempResults 暂存数组。
