LeetCode Top Interview Questions 329. Longest Increasing Path in a Matrix (Java版; Hard)

雨点打透心脏的1/2处 2023-07-02 10:29 1阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 329. Longest Increasing Path in a Matrix (Java版; Hard) ##

#### 题目描述 ####

Given an integer matrix, find the length of the longest increasing path.
    
    From each cell, you can either move to four directions: left, right, up or down. You may NOT move 
    diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
    
    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.

#### 第一次做; 动态规划; dp的重点是按序进行; 使用匿名函数写堆的比较器; dp\[i\]\[j\]表示以(i,j)结尾的最长路径; 这道题最好的方法是使用memo数据, 并不是dp ####

//动态规划版本: dp[i][j]表示以(i,j)结尾的最长路径; dp的关键是按序进行, 本题中的顺序是先处理值小的数, 再处理值大的数, 所以先把数排个序
    class Solution { 
        public int longestIncreasingPath(int[][] matrix) { 
            if(matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0)
                return 0;
            //按照value升序排序; 使用了匿名函数, 学习这种写法, 面试不扣分项
            Queue<int[]> queue = new PriorityQueue<int[]>((a,b)->a[0]-b[0]);
            int n = matrix.length, m = matrix[0].length;
            for(int i=0; i<n; i++){ 
                for(int j=0; j<m; j++){ 
                    //数组的三个元素分别是value, 行坐标, 列坐标
                    queue.add(new int[]{ matrix[i][j], i, j});
                }
            }
            //dp[i][j]表示以(i,j)结尾的最长路径
            int[][] dp = new int[n][m];
            // for(int[] a : dp){ 
            // //初始时,dp[i][j]==1,表示以(i,j)结尾的最长路径为1
            // Arrays.fill(a,1);
            // }
            int max=0;
            while(!queue.isEmpty()){ 
                int[] cur = queue.poll();
                int value = cur[0];
                int i = cur[1];
                int j = cur[2];
                //当前以(i,j)结尾的路径长度
                int curMax = 1;
                //上下左右
                if(i-1>=0 && value > matrix[i-1][j]){ 
                    curMax = Math.max(curMax, 1+dp[i-1][j]);
                }
                if(i+1<n && value > matrix[i+1][j]){ 
                    curMax = Math.max(curMax, 1+dp[i+1][j]);
                }
                if(j-1>=0 && value > matrix[i][j-1]){ 
                    curMax = Math.max(curMax, 1+dp[i][j-1]);
                }
                if(j+1<m && value > matrix[i][j+1]){ 
                    curMax = Math.max(curMax, 1+dp[i][j+1]);
                }
                //更新dp
                dp[i][j] = curMax;
                //更新max
                max = Math.max(max, curMax);
            }
            return max;
        }
    }

#### 第一次做; 待优化的暴力递归, 使用memo数组记忆已经遍历过的位置, 拿空间换时间; 跟暴力递归的区别: 1)不再需要cur作为参数, 2)不再需要全局变量max; 最重要的是想清楚递归函数的递归逻辑 ####

//使用memo[][]记录已经遍历过的点的结果
    class Solution { 
        public int longestIncreasingPath(int[][] matrix) { 
            //input check 
            if(matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0)
                return 0;
            int n=matrix.length, m=matrix[0].length;
            int[][] memo = new int[n][m];
            int max = 0;
            for(int i=0; i<n; i++){ 
                for(int j=0; j<m; j++){ 
                    max = Math.max(max, core(memo,matrix, i, j));
                }
            }
            return max;
            
        }
        //核心:要想清楚递归函数的递归逻辑, 本题中的递归逻辑: 返回从(i,j)出发的最长路径
        //cur表示的是当前路径的长度 递归函数逻辑: 返回以(i,j)为起点的最长路径
        public int core(int[][] memo, int[][] matrix, int i, int j){ 
            //base case
            if(memo[i][j] != 0)
                return memo[i][j];
            //max记录从(i,j)周围四个点出发, 能够返回的最大长度
            int max = 0;
            //四种移动方式不是互斥的, 而是都可以尝试
            //上
            if(isValid(matrix,i-1,j) && matrix[i-1][j] > matrix[i][j]){ 
                //新条件新递归
                max = Math.max(max, core(memo,matrix, i-1, j));
            }
            //下
            if(isValid(matrix,i+1,j)&&matrix[i+1][j]>matrix[i][j]){ 
                max = Math.max(max, core(memo,matrix, i+1, j));
            }
            //左
            if(isValid(matrix,i,j-1)&&matrix[i][j-1]>matrix[i][j]){ 
                max = Math.max(max, core(memo,matrix,i,j-1));
            }
            //右
            if(isValid(matrix,i,j+1)&&matrix[i][j+1]>matrix[i][j]){ 
                max = Math.max(max, core(memo,matrix,i,j+1));
            }
            //从(i,j)周围四个点出发能够返回的最大长度, 加上(i,j)这个点, 从而构成从(i,j)出发的最长路径
            memo[i][j] = max+1;
            return memo[i][j];
        }
        public boolean isValid(int[][] matrix, int i, int j){ 
            int n=matrix.length, m=matrix[0].length;
            return i>=0 && i<n && j>=0 && j<m;
        }
    }

#### 第一次做; 暴力递归, 超时, 135 / 138; 关键: 什么时候更新max? 每次进入递归时更新max; cur是当前路径的长度; 四种选择是独立的, 不是互斥的!! ####

//暴力递归
    class Solution { 
        public int max = 0;
        public int longestIncreasingPath(int[][] matrix) { 
            //input check 
            if(matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0)
                return 0;
            int n=matrix.length, m=matrix[0].length;
            for(int i=0; i<n; i++){ 
                for(int j=0; j<m; j++){ 
                    core(matrix, i, j, 1);
                }
            }
            return max;
            
        }
        //cur表示的是当前路径的长度
        public void core(int[][] matrix, int i, int j, int cur){ 
            //注意在哪里更新, 进入递归时就更新
            max = Math.max(max, cur);
            //四种移动方式不是互斥的, 而是都可以尝试
            //上
            if(isValid(matrix,i-1,j) && matrix[i-1][j] > matrix[i][j]){ 
                core(matrix, i-1, j, cur+1);
            }
            //下
            if(isValid(matrix,i+1,j)&&matrix[i+1][j]>matrix[i][j]){ 
                core(matrix, i+1, j, cur+1);
            }
            //左
            if(isValid(matrix,i,j-1)&&matrix[i][j-1]>matrix[i][j]){ 
                core(matrix,i,j-1,cur+1);
            }
            //右
            if(isValid(matrix,i,j+1)&&matrix[i][j+1]>matrix[i][j]){ 
                core(matrix,i,j+1, cur+1);
            }
        }
        public boolean isValid(int[][] matrix, int i, int j){ 
            int n=matrix.length, m=matrix[0].length;
            return i>=0 && i<n && j>=0 && j<m;
        }
    }

#### [动态规划题解][Link 1]; dp\[i\]\[j\]表示以(i,j)结尾的最长路径; 比较器是用匿名函数写的; dp的重点是需要按序进行，保证大的dp可以依赖小的dp ####

看大家用dfs记忆搜索的比较多，这里提供一个纯dp的思路。先按照元素值大小进行排序，同时记录元素的值，x，y坐标。再以元素值从小到大的顺序在matrix矩阵中进行dp累积。
    
    dp的重点是需要按序进行，保证大的dp可以依赖小的dp，在这里表现为，递增较大的元素需要在较小元素计算后再计算，所以使用最小堆弹出当前最小元素，并使用记录的x,y坐标到matrix矩阵上判断周边元素大小，完成dp累积

public int longestIncreasingPath(int[][] matrix) { 
            if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
                return 0;
            //元素入最小堆，数组下标0-value，数组下标1-matrix中y坐标，数组下标2-matrix中x坐标，最小堆以value排序
            Queue<int[]> minDump = new PriorityQueue<int[]>((pre,next) -> pre[0] - next[0]);
            for(int y = 0; y < matrix.length; y++){ 
                for(int x = 0; x < matrix[0].length; x++){ 
                    minDump.offer(new int[]{ matrix[y][x],y,x});
                }
            }
            //dp(记录当前元素累积到的最大递增路径长度)
            int[][] dp = new int[matrix.length][matrix[0].length];
            //实时记录最大路径，作为返回值返回
            int maxLength = 0; 
            //元素从小到大开始dp(保证大的元素排在小的元素后被累积)
            while(minDump.size() > 0){ 
                int[] curElement = minDump.poll();
                int value = curElement[0];
                int y = curElement[1];
                int x = curElement[2];
                int curMax = 1;
                //四个方向比较最大路径(如果matrix元素大于周边的元素，则最长路径在周边dp的基础上+1)
                if(y > 0 && value > matrix[y - 1][x])
                    curMax = Math.max(curMax,dp[y - 1][x] + 1);
                if(y < matrix.length - 1 && value > matrix[y + 1][x])
                    curMax = Math.max(curMax,dp[y + 1][x] + 1);
                if(x > 0 && value > matrix[y][x - 1])
                    curMax = Math.max(curMax,dp[y][x - 1] + 1);
                if(x < matrix[0].length - 1 && value > matrix[y][x + 1])
                    curMax = Math.max(curMax,dp[y][x + 1] + 1);
                //累积dp
                dp[y][x] = curMax;
                //实时记录最大值
                maxLength = Math.max(maxLength,curMax);
            }
            return maxLength;
        }

#### [动态规划][Link 2], 主要看看dp\[i\]\[j\]的含义 ####

![format_png][]

#### [力扣题解][Link 3]; 三种方法: 暴力递归; memo优化; 动态规划; 注意时间复杂度和空间复杂度的分析; 上下左右的遍历学一下, 别写4个if了 ####

![format_png 1][]

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/javaban-chun-dp-by-fansir/
[Link 2]: https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/san-chong-jie-fa-by-jason-2-4/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS8yOGE0OGE3NTE3ODJhOTRiMTQzYjUxNGI2MmQ4MjMzNC94bWxub3RlL0FEOERGM0IyRTVGRDRDRUI4NzQxRjNDNDNGMThCNkJBLzU2Mjc0?x-oss-process=image/format,png
[Link 3]: https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/ju-zhen-zhong-de-zui-chang-di-zeng-lu-jing-by-leet/
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS8yOGE0OGE3NTE3ODJhOTRiMTQzYjUxNGI2MmQ4MjMzNC94bWxub3RlLzE3RTEyN0U2QkMyMTQ5QzFBN0FGRDU2QkYwRjAxODBBLzU2MjY1?x-oss-process=image/format,png