矩阵中的最长递增路径

二 题目

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 

你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:
输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:
输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出: 4 
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var longestIncreasingPath = function(matrix) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

深度优先搜索：

/**
 * @param {number[][]} matrix
 * @return {number}
 */
/**
 * 思考：
 * 1. 递增标明数字至少 + 1
 * 2. 可以使用 DPS 统计每个数字能走向的最深路径（BFS 怕爆内存）
 * 3. 每次找完路径后更新最长路径
 * 反思：
 * 1. 这不是一个完整的矩阵，N 的长度需要重新定义？打个问号
 * 2. DFS 也会超出时间限制，需要进一步优化（使用 meno 记忆每个点的深度）
 */
const longestIncreasingPath = (matrix) => {
  // 空数组
  if (!matrix.length) {
    return 0;
  }

  // 横纵坐标
  const M = matrix.length;
  const N = matrix[0].length;

  // 优化：加入记忆模块
  const meno = Array.from(Array(M), () => Array.from(Array(N), () => {}));

  // 结果
  let result = 1;

  const dfs = (m, n, depth = 1) => {
    if (meno[m][n]) {
      return meno[m][n];
    }
    console.log(m, n, depth);
    const value = matrix[m][n];
    let top = 1, bottom = 1, left = 1, right = 1;
    // 向上
    if (matrix[m - 1] && matrix[m - 1][n] > value) {
      top = Math.max(depth, dfs(m - 1, n, depth) + 1);
    }
    // 向下
    if (matrix[m + 1] && matrix[m + 1][n] > value) {
      bottom = Math.max(depth, dfs(m + 1, n, depth) + 1);
    }
    // 向左
    if (matrix[m][n - 1] > value) {
      left = Math.max(depth, dfs(m, n - 1, depth) + 1);
    }
    // 向右
    if (matrix[m][n + 1] > value) {
      right = Math.max(depth, dfs(m, n + 1, depth) + 1);
    }
    meno[m][n] = Math.max(depth, top, bottom, left, right);
    return Math.max(depth, top, bottom, left, right);
  };

  // 遍历矩阵
  for (let i = 0; i < M; i++) {
    for (let j = 0; j < N; j++) {
      console.log('------');
      result = Math.max(result, dfs(i, j, 1));
    }
  }

  return result;
};

// console.log(longestIncreasingPath(
//   [
//     [9,9,4],
//     [6,6,8],
//     [2,1,1]
//   ] 
// )); // 4
// console.log(longestIncreasingPath(
//   [
//     [3,4,5],
//     [3,2,6],
//     [2,2,1]
//   ]
// )); // 4
console.log(longestIncreasingPath(
  [
    [0,1,2,3,4,5,6,7,8,9],
    [19,18,17,16,15,14,13,12,11,10],
    [20,21,22,23,24,25,26,27,28,29],
    [39,38,37,36,35,34,33,32,31,30],
    [40,41,42,43,44,45,46,47,48,49],
    [59,58,57,56,55,54,53,52,51,50],
    [60,61,62,63,64,65,66,67,68,69],
    [79,78,77,76,75,74,73,72,71,70],
    [80,81,82,83,84,85,86,87,88,89],
    [99,98,97,96,95,94,93,92,91,90],
    [100,101,102,103,104,105,106,107,108,109],
    [119,118,117,116,115,114,113,112,111,110],
    [120,121,122,123,124,125,126,127,128,129],
    [139,138,137,136,135,134,133,132,131,130],
    [0,0,0,0,0,0,0,0,0,0]
  ]
));

四 统计分析

本题不需要统计分析。

五 套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。