剑指 Offer II 112. 最长递增路径
comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20112.%20%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E8%B7%AF%E5%BE%84/README.md
剑指 Offer II 112. 最长递增路径
题目描述
给定一个 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.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
注意：本题与主站 329 题相同： https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
解法
方法一
Python3
from itertools import pairwise
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
dirs=(0,-1,0,1,0)
@cache
def dfs(i,j):
path=1 #本身长度1
for dx,dy in pairwise(dirs):
nx,ny=i+dx,j+dy
if 0<=nx<m and 0<=ny<n:
if matrix[nx][ny]>matrix[i][j]:
path=max(path,1+dfs(nx, ny)) # 【核心】从众多条路径中找到最长的
return path
res=0
m,n=len(matrix),len(matrix[0])
for i in range(m):
for j in range(n):
res=max(res,dfs(i,j))
return res
Java
class Solution {
private int[][] memo;
private int[][] matrix;
private int m;
private int n;
public int longestIncreasingPath(int[][] matrix) {
this.matrix = matrix;
m = matrix.length;
n = matrix[0].length;
memo = new int[m][n];
for (int i = 0; i < m; ++i) {
Arrays.fill(memo[i], -1);
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans = Math.max(ans, dfs(i, j));
}
}
return ans;
}
private int dfs(int i, int j) {
if (memo[i][j] != -1) {
return memo[i][j];
}
int ans = 1;
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
ans = Math.max(ans, dfs(x, y) + 1);
}
}
memo[i][j] = ans;
return ans;
}
}
C++
class Solution {
public:
vector<vector<int>> memo;
vector<vector<int>> matrix;
int m;
int n;
int longestIncreasingPath(vector<vector<int>>& matrix) {
m = matrix.size();
n = matrix[0].size();
memo.resize(m, vector<int>(n, -1));
this->matrix = matrix;
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = max(ans, dfs(i, j));
return ans;
}
int dfs(int i, int j) {
if (memo[i][j] != -1) return memo[i][j];
int ans = 1;
vector<int> dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j])
ans = max(ans, dfs(x, y) + 1);
}
memo[i][j] = ans;
return ans;
}
};
Go
func longestIncreasingPath(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
memo := make([][]int, m)
for i := range memo {
memo[i] = make([]int, n)
for j := range memo[i] {
memo[i][j] = -1
}
}
ans := -1
var dfs func(i, j int) int
dfs = func(i, j int) int {
if memo[i][j] != -1 {
return memo[i][j]
}
ans := 1
dirs := []int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j] {
ans = max(ans, dfs(x, y)+1)
}
}
memo[i][j] = ans
return ans
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
ans = max(ans, dfs(i, j))
}
}
return ans
}
Swift
class Solution {
private var memo: [[Int]] = []
private var matrix: [[Int]] = []
private var m: Int = 0
private var n: Int = 0
func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
self.matrix = matrix
m = matrix.count
n = matrix[0].count
memo = Array(repeating: Array(repeating: -1, count: n), count: m)
var ans = 0
for i in 0..<m {
for j in 0..<n {
ans = max(ans, dfs(i, j))
}
}
return ans
}
private func dfs(_ i: Int, _ j: Int) -> Int {
if memo[i][j] != -1 {
return memo[i][j]
}
var ans = 1
let dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for (dx, dy) in dirs {
let x = i + dx, y = j + dy
if x >= 0, x < m, y >= 0, y < n, matrix[x][y] > matrix[i][j] {
ans = max(ans, dfs(x, y) + 1)
}
}
memo[i][j] = ans
return ans
}
}