题目

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).

Example 1:

image.png

  1. Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
  2. Output: 4
  3. Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

image.png

  1. Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
  2. Output: 4
  3. Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

  1. Input: matrix = [[1]]
  2. Output: 1

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31 - 1

题意

给定一个矩阵，可以从任一位置出发得到一条递增的路径，求最长路径的长度。

思路

DFS+记忆化很容易解决。

代码实现

Java

  1. class Solution {
  2.     private int[] xShift = {0, -1, 0, 1};
  3.     private int[] yShift = {-1, 0, 1, 0};
  4.     private int m, n;
  6.     public int longestIncreasingPath(int[][] matrix) {
  7.         m = matrix.length;
  8.         n = matrix[0].length;
  10.         int ans = 0;
  11.         int[][] record = new int[m][n];
  13.         for (int i = 0; i < m; i++) {
  14.             for (int j = 0; j < n; j++) {
  15.                 ans = Math.max(ans, dfs(matrix, i, j, record));
  16.             }
  17.         }
  19.         return ans;
  20.     }
  22.     private int dfs(int[][] matrix, int x, int y, int[][] record) {
  23.         if (record[x][y] > 0) return record[x][y];
  25.         record[x][y] = 1;
  26.         for (int i = 0; i < 4; i++) {
  27.             int nx = x + xShift[i], ny = y + yShift[i];
  28.             if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[x][y] < matrix[nx][ny]) {
  29.                 record[x][y] = Math.max(record[x][y], 1 + dfs(matrix, nx, ny, record));
  30.             }
  31.         }
  32.         return record[x][y];
  33.     }
  34. }