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

---

题目链接：2713. 矩阵中严格递增的单元格数

代码如下：

//动态规划＋优化
//参考链接:https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/solutions/2286920/dong-tai-gui-hua-you-hua-pythonjavacgo-b-axv0
class Solution 
{
public:int maxIncreasingCells(vector<vector<int>>& mat) {map<int,vector<pair<int,int>>> graph;for(int i=0;i<mat.size();i++){for(int j=0;j<mat[0].size();j++){// 相同元素放在同一组，统计位置graph[mat[i][j]].emplace_back(i,j);}}vector<int> row_max(mat.size()),col_max(mat[0].size());for(auto& [_,pos]:graph){vector<int> mx;// 先把最大值算出来，再更新 row_max 和 col_maxfor(auto& [i,j]:pos){mx.push_back(max(row_max[i],col_max[j])+1);}for(int k=0;k<pos.size();k++){auto& [i,j]=pos[k];row_max[i]=max(row_max[i],mx[k]);// 更新第 i 行的最大 f 值col_max[j]=max(col_max[j],mx[k]);// 更新第 j 列的最大 f 值}}return ranges::max(row_max);}
};