作者推荐
本文涉及知识点
题目
给定一个 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
动态规划
时间复杂度: O(nmlog(nm))。
一，将行列压缩成一维。m_c*r+c。
二，建立图论的临接表。两个节点4连接，值小的指向值大的。
三，从值大的到值小的动态规划。
动态规划的细节，方便检查
| 动态规划的状态表示 | dp[i]记录当前节点为起点的最长路径长度 |
| 动态规划的转移方程 | 1+ max(dp[j]) j 是邻接表的节点 |
| 动态规划的初始状态 | 无需初始化，所有节点都会处理。 |
| 动态规划的填表顺序 | 从值大到值小处理，,确保动态规划的无后效性 |
| 动态规划的返回值 | dp的最大值 |
注意：最小值不一定是最大长度。比如：
| 1 | 9 | 2 |
| 9 | 4 | 3 |
1只能1->9
2可以2->3->4
代码
核心代码
class CEnumGridEdge { public: void Init() { for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { Move(r, c, r + 1, c); Move(r, c, r - 1, c); Move(r, c, r, c + 1); Move(r, c, r, c - 1); } } } protected: CEnumGridEdge(int r, int c) :m_r(r), m_c(c) { } void Move(int preR, int preC, int r, int c) { if ((r < 0) || (r >= m_r)) { return; } if ((c < 0) || (c >= m_c)) { return; } OnEnumEdge(preR, preC, r, c); }; virtual void OnEnumEdge(int preR, int preC, int r, int c) = 0; const int m_r, m_c; }; class CMatToNeibo : public CEnumGridEdge { public: CMatToNeibo(const vector<vector<int>>& matrix) :CEnumGridEdge(matrix.size(), matrix[0].size()), m_mat(matrix), m_NodeCount(m_r* m_c), m_vNeiBo(m_NodeCount) { for (int r = 0; r < m_r; r++) { for (int c = 0; c < m_c; c++) { m_mValueToIndex.emplace(matrix[r][c], m_c * r + c); } } } int Do() { Init(); vector<int> dp(m_NodeCount); for (const auto& [_tmp, inx] : m_mValueToIndex) { int iMax = 0; for (const auto& next : m_vNeiBo[inx]) { iMax = max(iMax, dp[next]); } dp[inx] = iMax + 1; } return *std::max_element(dp.begin(),dp.end()); } const int m_NodeCount; vector<vector<int>> m_vNeiBo; const vector<vector<int>>& m_mat; std::multimap<int, int, greater<>> m_mValueToIndex; protected: virtual void OnEnumEdge(int preR, int preC, int r, int c) { if (m_mat[preR][preC] < m_mat[r][c]) { m_vNeiBo[m_c * preR + preC].emplace_back(m_c * r + c); } } }; class Solution { public: int longestIncreasingPath(vector<vector<int>>& matrix) { CMatToNeibo mn(matrix); return mn.Do(); } };
2023年1月
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;
};
