[LeetCode] Longest Increasing Path in a Matrix 矩阵中的最长递增路径

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]


Return 4

The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]


Return 4

The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

class Solution {
public:
vector<vector<int>> dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
int longestIncreasingPath(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int res = 1, m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
res = max(res, dfs(matrix, dp, i, j));
}
}
return res;
}
int dfs(vector<vector<int>> &matrix, vector<vector<int>> &dp, int i, int j) {
if (dp[i][j]) return dp[i][j];
int mx = 1, m = matrix.size(), n = matrix[0].size();
for (auto a : dirs) {
int x = i + a[0], y = j + a[1];
if (x < 0 || x >= m || y < 0 |a| y >= n || matrix[x][y] <= matrix[i][j]) continue;
int len = 1 + dfs(matrix, dp, x, y);
mx = max(mx, len);
}
dp[i][j] = mx;
return mx;
}
};

class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size(), res = 1;
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j ) {
if (dp[i][j] > 0) continue;
queue<pair<int, int>> q{{{i, j}}};
int cnt = 1;
while (!q.empty()) {
++cnt;
int len = q.size();
for (int k = 0; k < len; ++k) {
auto t = q.front(); q.pop();
for (auto dir : dirs) {
int x = t.first + dir[0], y = t.second + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[t.first][t.second] || cnt <= dp[x][y]) continue;
dp[x][y] = cnt;
res = max(res, cnt);
q.push({x, y});
}
}
}
}
}
return res;
}
};

|
22天前
|

20 0
|
1月前
|

LeetCode题目113:多种算法实现 路径总和ll
LeetCode题目113:多种算法实现 路径总和ll
18 1
|
1月前
|

24 4
|
1月前
|

25 2
|
1月前
|

LeetCode 题目 62：不同路径【python】
LeetCode 题目 62：不同路径【python】
22 2
|
1月前
|

LeetCode 题目 120：三角形最小路径和
LeetCode 题目 120：三角形最小路径和
15 0
|
1月前
|

LeetCode题目112:多种算法实现路径总与改进过程
LeetCode题目112:多种算法实现路径总与改进过程
12 0
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
29 2
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
35 2
|
1月前
|

【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
25 1