329. Longest Increasing Path in a Matrix

[Tcdian]

329. Longest Increasing Path in a Matrix

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

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

Example 1

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

Example 2

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

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var longestIncreasingPath = function(matrix) {
    if (matrix.length === 0 || matrix[0].length === 0) {
        return 0;
    }
    const positions = [];
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            positions.push([i, j]);
        }
    }
    positions.sort(([x1, y1], [x2, y2]) => matrix[x1][y1] - matrix[x2][y2]);
    const dp = Array.from(new Array(matrix.length), () => new Array(matrix[0].length).fill(1));
    const directions = [-1, 0, 1, 0, -1];
    let result = 1;
    for (let i = 0; i < positions.length; i++) {
        for(let d = 0; d < 4; d++) {
            const [x, y] = positions[i];
            const directionX = directions[d] + x;
            const directionY = directions[d + 1] + y;
            if (
                directionX >= 0 && directionX < matrix.length
                    && directionY >= 0 && directionY < matrix[0].length
                    && matrix[x][y] < matrix[directionX][directionY]
            ) {
                dp[directionX][directionY] = Math.max(dp[x][y] + 1, dp[directionX][directionY]);
                result = Math.max(dp[directionX][directionY], result);
            }
        }
    }
    return result;
};

• TypeScript Solution

function longestIncreasingPath(matrix: number[][]): number {
    if (matrix.length === 0 || matrix[0].length === 0) {
        return 0;
    }
    const positions: [number, number][] = [];
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            positions.push([i, j]);
        }
    }
    positions.sort(([x1, y1], [x2, y2]) => matrix[x1][y1] - matrix[x2][y2]);
    const dp: number[][] = Array.from(new Array(matrix.length), () => new Array(matrix[0].length).fill(1));
    const directions = [-1, 0, 1, 0, -1];
    let result = 1;
    for (let i = 0; i < positions.length; i++) {
        for(let d = 0; d < 4; d++) {
            const [x, y] = positions[i];
            const directionX = directions[d] + x;
            const directionY = directions[d + 1] + y;
            if (
                directionX >= 0 && directionX < matrix.length
                    && directionY >= 0 && directionY < matrix[0].length
                    && matrix[x][y] < matrix[directionX][directionY]
            ) {
                dp[directionX][directionY] = Math.max(dp[x][y] + 1, dp[directionX][directionY]);
                result = Math.max(dp[directionX][directionY], result);
            }
        }
    }
    return result;
};