我要招人

去企业版

首页 > 试题广场 >

矩阵最长递增路径

[编程题]矩阵最长递增路径

热度指数：53317 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。并输出这条最长路径的长度。

这个路径必须满足以下条件：

1. 对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外。

2. 你不能走重复的单元格。即每个格子最多只能走一次。

数据范围： $1 \le n,m \le 1000$ ， $0 \le matrix[i][j] \le 1000$

进阶：空间复杂度 $O(nm)$ ，时间复杂度 $O(nm)$

例如：当输入为[[1,2,3],[4,5,6],[7,8,9]]时，对应的输出为5，

其中的一条最长递增路径如下图所示：

示例1

输入

[[1,2,3],[4,5,6],[7,8,9]]

输出

说明

1->2->3->6->9即可。当然这种递增路径不是唯一的。

示例2

输入

[[1,2],[4,3]]

输出

说明

 1->2->3->4

备注:

矩阵的长和宽均不大于1000，矩阵内每个数不大于1000

算法知识视频讲解

牛客题解官

发表于 2022-04-22 12:33:50

精华题解题目主要信息：矩阵内是非负数，求最长的递增路径的长度移动方向可以是上下左右，不能超出边界，这将是递归的判定条件同一条路径不能有重复的单元格，需要有记忆举一反三：学习完本题的思路你可以解决如下题目： BM57. 岛屿数量方法一：深度优先搜索(推荐使用) 知识点：深度优先搜索（dfs）展开全文

sugar-tx

发表于 2021-02-09 15:09:41

解题思路对于矩阵中某一点，我们可以沿上下左右四个方向（边界情况除外）前进，在前进之后如果所在点的值小于等于上一点的值，那么说明此路径无效，返回上一点，并选取其他路径进行尝试。因为每个点都有可能是路径的头，所以需要对矩阵中的所有点为头进行查找。 import java.util.*; publi 展开全文

youxiwang

发表于 2022-03-07 14:35:56

从矩阵中的每一点开始一遍dfs, dfs时记录目前为止最长递增路径对于current每个neighbor, 继续dfs的条件是: 1. neighbor没有越界 2. neighbor的值比current大注意：这题dfs不需要记录visited, 因为能走的路径是单向的(因为condi 展开全文

Peterliang

发表于 2021-11-07 16:53:20

题意分析给出一个二维矩阵，矩阵的每个位置有一个数字，我们需要任意选择一个起点，然后从这个起点出发，每次只能走比当前数字更大的位置，问我们最多可以走多少步。每次走的位置只能是上下左右四个方向，同时不能越界。每个格子最多只能走一次。思路分析一个DFS的操作，我们发现，我们可以枚举某一个起点展开全文

有名

发表于 2021-08-05 15:24:50

描述给定一个n行m列矩阵 matrix，矩阵内所有数均为非负整数。求一条路径，该路径上所有数是递增的。这个路径必须满足以下条件：对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外。你不能走重复的单元格。即每个格子最多只能走一次。数据范围：展开全文

AmireuxSTT

发表于 2022-03-26 17:01:03

import java.util.*; public class Solution { int maxStep = 0; public int solve (int[][] matrix) { //因为不知道起始点，所以所有的点都要试一遍 for (i 展开全文

诗云panther

发表于 2021-08-13 17:18:41

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 递增路径的最大长度 * @param matrix int整型二维数组描述矩阵的每个数展开全文

-Nil-

发表于 2022-05-02 09:43:50

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 递增路径的最大长度 * @param matrix int整型二维数组描述矩阵的每个数 * @return int整型 */ //DFS+备忘录 func solve( matrix [][]int 展开全文

讲道理的豹子说这不是bug

发表于 2023-08-09 13:29:14

方法：dfs（深度优先搜索）既然是查找最长的递增路径长度，那我们首先要找到这个路径的起点，起点不好直接找到，就从上到下从左到右遍历矩阵的每个元素。然后以每个元素都可以作为起点查找它能到达的最长递增路径。如何查找以某个点为起点的最长递增路径呢？我们可以考虑深度优先搜索，因为我们查找递增路径的时候，每次展开全文

空中转体一周半

发表于 2022-03-02 12:20:04

暴力递归，深度优先，遍历数组的每一个格子，把符合条件的邻居格子加入递归即可。 public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 递增路径的最大长度 * @param ma 展开全文

fred-coder

发表于 2021-12-15 00:46:14

记忆化搜索，根据题意可利用 dfs 进行求解,因为路径是递增的,已走过的路径可缓存,利用递归 + 备忘录的方式求解 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 递增路径的最大长度 # @param matrix int整型二维数组描述矩阵的每个数 # 展开全文

问题信息

动态规划图 dfs

难度：

100条回答 763收藏 5261浏览

通过挑战的用户

查看代码

牛客89427...

2022-09-16 19:04:17
希望奇迹发生的...

2022-09-16 14:12:25
xxdev

2022-09-16 13:57:28
就是要HAPPY

2022-09-16 11:28:55
牛客45609...

2022-09-16 10:12:05

矩阵最长递增路径

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题