涉及知识点
题目
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：
输入：matrix = [[1]]
输出：1
参数范围：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 231 - 1
2023年一月版
class Solution { public: int longestIncreasingPath(vector<vector>& matrix) { m_r = matrix.size(); m_c = matrix[0].size(); m_dp.assign(m_r, vector(m_c, -1)); std::map<int,vector<pair<int,int>>> mVRC; for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { mVRC[matrix[r][c]].emplace_back(r, c); } } for (auto& it : mVRC) { for (auto& rc : it.second) { m_dp[rc.first][rc.second] = Test(matrix, rc.first, rc.second); } } int iMax = 0; for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { iMax = max(iMax, m_dp[r][c]); } } return iMax; } int Test(const vector<vector>& matrix,int r, int c) { int iMax = 0; if ((r > 0) && (matrix[r][c] > matrix[r - 1][c])) { iMax = max(iMax,m_dp[r-1][c] ); } if ((r +1 < m_r ) && (matrix[r][c] > matrix[r + 1][c])) { iMax = max(iMax, m_dp[r + 1][c]); } if ((c > 0) && (matrix[r][c] > matrix[r][c-1])) { iMax = max(iMax, m_dp[r][c-1]); } if ((c + 1 < m_c) && (matrix[r][c] > matrix[r][c + 1])) { iMax = max(iMax, m_dp[r][c + 1]); } return iMax + 1; } int m_r; int m_c; vector<vector> m_dp; };
2023年8月版
class Solution { public: int longestIncreasingPath(vector<vector>& matrix) { m_r = matrix.size(); m_c = matrix.front().size(); m_iMaskNum = m_r * m_c; //生成邻接表 vector<vector> vNeiBo(m_iMaskNum); vector vInDeg(m_iMaskNum); for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { auto Add = [this,&matrix, &vNeiBo,&vInDeg](int curMask, int curValue, int r, int c) { if ((r < 0) || (r >= m_r)) { return; } if ((c < 0) || (c >= m_c)) { return; } if (curValue > matrix[r][c]) { vNeiBo[r * m_c + c].emplace_back(curMask); vInDeg[curMask]++; } }; Add(r * m_c + c, matrix[r][c], r + 1, c); Add(r * m_c + c, matrix[r][c], r - 1, c); Add(r * m_c + c, matrix[r][c], r, c + 1); Add(r * m_c + c, matrix[r][c], r, c - 1); } } //top排序 queue que; vector vLen(m_iMaskNum, 0); for (int i = 0; i < m_iMaskNum; i++) { if (0 == vInDeg[i]) { que.emplace(i); vLen[i] = 1; } } while (que.size()) { const int cur = que.front(); que.pop(); for (const auto& next : vNeiBo[cur]) { if (–vInDeg[next] == 0) { vLen[next] = vLen[cur] + 1; que.emplace(next); } } } return *std::max_element(vLen.begin(), vLen.end()); } int m_r; int m_c; int m_iMaskNum; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
