题目描述
题目链接:329. Longest Increasing Path in a Matrix
Given an
m x n
integers matrix, return the length of the longest increasing path inmatrix
.From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
例子
例子 1
Input:
matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output:4
Explanation: The longest increasing path is[1, 2, 6, 9]
.
例子 2
Input:
matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output:4
Explanation: The longest increasing path is[3, 4, 5, 6]
. Moving diagonally is not allowed.
例子 3
Input:
matrix = [[1]]
Output:1
Follow Up
Note
Constraints
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1
解题思路
这道题可以利用 DFS 结合记忆过程来求解,首先用等大的数组存储以每个位置为起点的最长上升路径的长度,初始为 0。然后遍历数组,对每一个位置,找到相邻且值比当前值大的位置作为下一个步候选位置递归的求解,返回该位置和长度。取四个方向中最长的长度并加 1 作为当前起点的长度。如果该位置的结果在之前的迭代中已经被求解并存储,则直接返回该结果即可。代码如下:
#include <vector>
class Solution {
public:
int longestIncreasingPath(std::vector<std::vector<int>>& matrix) {
directions =
std::vector<std::pair<int, int>>{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
max_lens = std::vector<std::vector<int>>(
matrix.size(), std::vector<int>(matrix[0].size(), 0));
int result = 1;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
result = std::max(result, dfs(matrix, i, j));
}
}
return result;
}
private:
std::vector<std::pair<int, int>> directions;
std::vector<std::vector<int>> max_lens;
int dfs(const std::vector<std::vector<int>>& matrix, int row, int col) {
if (max_lens[row][col] != 0) {
return max_lens[row][col];
}
int len = 1;
for (auto& dir : directions) {
int r = row + dir.first;
int c = col + dir.second;
if (r < 0 || r >= matrix.size() || c < 0 || c >= matrix[0].size())
continue;
if (matrix[r][c] > matrix[row][col]) {
len = std::max(len, 1 + dfs(matrix, r, c));
}
}
max_lens[row][col] = len;
return max_lens[row][col];
}
};
- 时间复杂度:
O(mn)
- 空间复杂度:
O(mn)
GitHub 代码同步地址: 329.LongestIncreasingPathInAMatrix.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions