Skip to content

Latest commit

 

History

History
160 lines (136 loc) · 4.49 KB

20200726-329.longest-increasing-path-in-a-matrix.md

File metadata and controls

160 lines (136 loc) · 4.49 KB

#329.longest-increasing-path-in-a-matrix

题目链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/

参考链接：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/ju-zhen-zhong-de-zui-chang-di-zeng-lu-jing-by-le-2/

题目

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

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例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]。注意不允许在对角线方向上移动。

解题

思路[1]深度优先搜索

  • 对每个单元格进行深度优先搜索，然后记录当前单元格开始的最长递增路径
  • 遍历所有单元格，如果有计算过的就使用记录的值
  • 最后取总共的最大值
  • 对每个单元格进行计算最长递增路径时，要考虑到边界问题，过程就是，判断上下左右的四个值，如果存在比他大的单元格，就返回1+比他的单元格，因为是4个方向，也要找最大值

代码

/**
 * @param {number[][]} matrix
 * @return {number}
 */
const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0]; // 0和1、1和0、0和-1、-1和0，四个方向
const longestIncreasingPath = (matrix) => {
  if (matrix.length == 0) return 0; // 矩阵中没有元素
  const m = matrix.length;
  const n = matrix[0].length;
  const memo = new Array(m);
  for (let i = 0; i < m; i++) memo[i] = new Array(n);
  let res = 1;                      // 路径长度至少为1
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {   // 对坐标(i,j)进行dfs
      res = Math.max(res, dfs(matrix, i, j, m, n, memo));
    }
  }
  return res;
};
const dfs = (matrix, i, j, m, n, memo) => {
  if (memo[i][j]) return memo[i][j];
  let max = 1;           // 以(i,j)为起点的路径，长度保底是1
  for (let k = 0; k < 4; k++) {
    const x = i + dx[k]; 
    const y = j + dy[k]; // 新的坐标
    if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
      max = Math.max(max, 1 + dfs(matrix, x, y, m, n, memo));
    }
  }
  return memo[i][j] = max;
};

思路[2]广度优先搜索+拓扑排序

  • 计算每个单元格对应的出度，即有多少条边从该单元格出发
  • 通过一个单元格遍历4个方向，能的到当前单元格的出度，即满足边界情况的前提下，他如果小于几个方向，就说明有几个出度
  • 每次遍历出度为0的单元格，将周围4个单元格的出度都减少，将其中为0的放入数组中，下层遍历
  • 一共遍历总层数就是最长递增长度

代码

/**
 * @param {number[][]} matrix
 * @return {number}
 */
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const longestIncreasingPath = (matrix) => {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    return 0;
  }
  const rows = matrix.length;
  const columns = matrix[0].length;
  let out = [];
  for(let i = 0; i < rows; i++){
    out[i] = []
    for(let j = 0; j < columns; j++){
      out[i][j] = 0;
      for(let dir of dirs){
        const newRow = i + dir[0], newColumn = j + dir[1];
        const judgeBorder = newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns;
        if(judgeBorder && matrix[newRow][newColumn] > matrix[i][j]){
        // 满足边界且比当前格小，则当前格出度+1
          out[i][j]++;
        }
      }
    }
  }
  let queue = []
  for(let i = 0; i < rows; i++){
    for(let j = 0; j < columns; j++){
      if(out[i][j] === 0){
        queue.push([i, j])
      }
    }
  }
  // 计算深度
  let ans = 0
  while(queue.length > 0){
    ans++;
    let length = queue.length;
    for(let i = 0; i < length; i++){
      let [row, column] = queue.shift();
      for(let dir of dirs){
        const newRow = row + dir[0], newColumn = column + dir[1];
        const judgeBorder = newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns;
        if(judgeBorder && matrix[newRow][newColumn] < matrix[row][column]){
        // 满足边界且比当前格小，则出度减少
          --out[newRow][newColumn];
          if (out[newRow][newColumn] == 0) {
              queue.push([newRow, newColumn]);
          }
        }
      }
    }
  }
  return ans
};

思考