0%

[Leetcode]329. Longest Increasing Path in a Matrix(C++)

题目描述

题目链接:329. Longest Increasing Path in a Matrix

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

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 作为当前起点的长度。如果该位置的结果在之前的迭代中已经被求解并存储,则直接返回该结果即可。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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