329. Longest Increasing Path in a Matrix

Leetcode

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

題目

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

解答

• 方法一

單純用 DFS 搜索，自己點的最長路徑會是上、下、左、右四格中的最長路徑再+1，邊界條件為超出矩陣邊界範圍以及四周格子的數字比自己小的狀況

var longestIncreasingPath = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    const dir = [
        {row: -1, col: 0},
        {row: 0, col: 1},
        {row: 1, col: 0},
        {row: 0, col: -1}
    ]
    const dfs = (row, col) => {
        let max = 1;
        for (let i=0; i<dir.length; i++) {
            const nextRow = row+dir[i].row;
            const nextCol = col+dir[i].col;
            // 邊界條件
            if (
                nextRow < 0 || 
                nextRow >= m || 
                nextCol < 0 || 
                nextCol >= n || 
                matrix[nextRow][nextCol] <= matrix[row][col]
            ) continue;
            max = Math.max(max, dfs(nextRow, nextCol) + 1)
        }
        return max;
    }
    
    let res = 1;
    for (let row=0; row<m; row++) {
        for (let col=0; col<n; col++) {
            res = Math.max(res, dfs(row, col));
        }
    }
    
    return res;
};

Time Limit Exceeded

• 方法二

優化 DFS，利用矩陣(dp) 記憶已經計算過最長路徑的格子，避免重複計算

var longestIncreasingPath = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = Array.from(new Array(m), () => Array(n).fill(-1));
    
    const dir = [
        {row: -1, col: 0},
        {row: 0, col: 1},
        {row: 1, col: 0},
        {row: 0, col: -1}
    ]
    const dfs = (row, col) => {
        if (dp[row][col] !== -1) return dp[row][col];
        let max = 1;
        for (let i=0; i<dir.length; i++) {
            const nextRow = row+dir[i].row;
            const nextCol = col+dir[i].col;
            if (
                nextRow < 0 ||
                nextRow >= m ||
                nextCol < 0 ||
                nextCol >= n ||
                matrix[nextRow][nextCol] <= matrix[row][col]
            ) continue;
            max = Math.max(max, dfs(nextRow, nextCol) + 1)
        }
        dp[row][col] = max;
        return max;
    }
    
    let res = 1;
    for (let row=0; row<m; row++) {
        for (let col=0; col<n; col++) {
            res = Math.max(res, dfs(row, col));
        }
    }
    
    return res;
};

Runtime: 100 ms, faster than 92.98% of JavaScript online submissions for Longest Increasing Path in a Matrix. O(mn)

Memory Usage: 43 MB, less than 84.02% of JavaScript online submissions for Longest Increasing Path in a Matrix. O(mn)

https://www.youtube.com/watch?v=yZGpDJlcxRA

• 方法三

利用 BFS 的方式解，這種方式比 DFS 複雜許多

1. 一樣遍歷所有矩陣元素

2. 每次遍歷時，新增一個 queue 儲存此次遍歷所會接觸到的元素 (FIFO)

3. 每次往四個方向找時，等於是新的一輪，步數 (cnt) 先加 1

4. 再把 queue 裡此輪的所有元素依序從頭拿出來 (queue.shift)，各元素依序往四個方向找，符合邊界條件的給予 cnt 值並且加入到 queue 的後方，等待下一輪遍歷

var longestIncreasingPath = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = Array.from(new Array(m), () => Array(n).fill(-1));
    
    const dir = [
        {row: -1, col: 0},
        {row: 0, col: 1},
        {row: 1, col: 0},
        {row: 0, col: -1}
    ]
    
    let res = 1;
    for (let row=0; row<m; row++) {
        for (let col=0; col<n; col++) {
            // 如果已經有值，代表之前有計算過，故此元素不可能為最小值的起點，所以可以略過
            // ex. 1 -> 6 -> 9 最大路徑是 3，所以沒必要從元素 6 再開始計算
            if (dp[row][col] > -1) continue;
            const queue = [{row, col}];
            let cnt = 1;
            while(queue.length) {
              cnt++;
              // 記得要先把 queue.length 拿出來，不然之後 queue.shift 會改變矩陣長度
              const queueLength = queue.length;
              // 記得把此輪所有 queue 的元素取出來(此輪元素的 cnt 值都一樣)
              for(let i=0; i<queueLength; i++) {
                const {row: nowRow, col: nowCol} = queue.shift();

                for (let dirIndex=0; dirIndex<dir.length; dirIndex++) {
                    const nextRow = nowRow+dir[dirIndex].row;
                    const nextCol = nowCol+dir[dirIndex].col;
                    // 多一個 cnt <= dp[nextRow][nextCol] 的判斷，避免多餘的重複計算
                    if (
                      nextRow < 0 || nextRow >= m ||
                      nextCol < 0 || nextCol >= n || 
                      matrix[nextRow][nextCol] <= matrix[nowRow][nowCol] || 
                      cnt <= dp[nextRow][nextCol]
                    ) continue;
                    dp[nextRow][nextCol] = cnt;
                    res = Math.max(res, cnt);
                    queue.push({row: nextRow, col: nextCol});
                }
              }
            }
        }
    }
    
    return res;
};

Runtime: 232 ms, faster than 18.14% of JavaScript online submissions for Longest Increasing Path in a Matrix.

Memory Usage: 46 MB, less than 54.19% of JavaScript online submissions for Longest Increasing Path in a Matrix.

https://www.cnblogs.com/grandyang/p/5148030.html

測資

let matrix = [[9,9,4],[6,6,8],[2,1,1]];
matrix = [[3,4,5],[3,2,6],[2,2,1]];
matrix = [[1]];

console.log(longestIncreasingPath(matrix));

參考資料

1. https://www.youtube.com/watch?v=yZGpDJlcxRA

2. https://www.cnblogs.com/grandyang/p/5148030.html