题目
给你一个下标从 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 <= 105
1 <= m * n <= 105
-105 <= mat[i][j] <= 105
分析
时间复杂度: O(mnlogmn)。初始化数据时间复杂度：O(nmlogmn)。枚举所有单元格时间复杂度O(mn)，处理每个单元格，时间复杂度O(n)。
变量解析
| mValueToRowCols | 各值对应的行列，按值降序排序 |
| vRowMax | 大于当前值的各行最大递增单元格数 |
| vColMax | 大于当前值的各列最大递增单元格数 |
| vBuf | 当前值各行列的最大递增单元格数 |
代码
class Solution { public: int maxIncreasingCells(vector<vector<int>>& mat) { m_r = mat.size(); m_c = mat.front().size(); std::map<int, vector<pair<int, int>>,greater<int>> mValueToRowCols; for (int r = 0; r < m_r ;r++) { for (int c = 0; c < m_c ; c++) { mValueToRowCols[mat[r][c]].emplace_back(r, c); } } vector<int> vRowMax(m_r), vColMax(m_c); vector<tuple<int, int, int>> vBuf; for (const auto& [tmp, v] : mValueToRowCols) { for (const auto& [r, c] : v) { const int iMax = max(vRowMax[r], vColMax[c]) + 1; vBuf.emplace_back(r, c, iMax); } for (const auto& [r, c, iMax] : vBuf) { vRowMax[r] = max(vRowMax[r], iMax); vColMax[c] = max(vColMax[c], iMax); } vBuf.clear(); } return *std::max_element(vRowMax.begin(), vRowMax.end()); } int m_r, m_c; };
测试用例
template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector<vector<int>> mat; { Solution slu; mat = { {3,1},{3,4} }; auto res = slu.maxIncreasingCells(mat); Assert(2, res); } { Solution slu; mat = { {1,1},{1,1} }; auto res = slu.maxIncreasingCells(mat); Assert(1, res); } { Solution slu; mat = mat = { {3,1,6},{-9,5,7} }; auto res = slu.maxIncreasingCells(mat); Assert(4, res); } { Solution slu; mat = mat = { {5, 2, 9},{-6, 2, -5},{-1, 0, -5} }; auto res = slu.maxIncreasingCells(mat); Assert(6, res); } }
超时代码示例
vector<int> vRowMax(m_r), vColMax(m_c); for (const auto& [tmp, v] : mValueToRowCols) { vector<int> vCurRowMax = vRowMax, vCurColMax = vColMax; for (const auto& [r, c] : v) { const int iMax = max(vRowMax[r], vColMax[c]) + 1; vCurRowMax[r]= max(vCurRowMax[r],iMax); vCurColMax[c] = max(vCurColMax[r],iMax); } vCurRowMax.swap(vRowMax); vCurColMax.swap(vColMax); }
vector 构造函数比较费事，执行mn次会超时。
2023年6月旧代码
class Solution { public: int maxIncreasingCells(vector& mat) { m_r = mat.size(); m_c = mat[0].size(); std::map < int, vector>,std::greater> mValueRowCol; for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { mValueRowCol[mat[r][c]].emplace_back(make_pair( r, c )); } } vector vPreRows(m_r, 0), vPreCols(m_c, 0); int iMaxRet = 0; std::queue > que; for ( auto it : mValueRowCol) { for (const auto& pr : it.second) { int iRet = std::max(vPreRows[pr.first],vPreCols[pr.second])+1 ; iMaxRet = max(iMaxRet, iRet); que.emplace(pr.first, pr.second, iRet); } while (que.size()) { const int r = get<0>(que.front()); const int c = get<1>(que.front()); const int iRet = get<2>(que.front()); que.pop(); vPreRows[r] = max(vPreRows[r] ,iRet); vPreCols[c] = max(vPreCols[c],iRet); } }
return iMaxRet; } int m_r, m_c;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
