329. Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix

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:

nums = [ [9,9,4], [6,6,8], [2,1,1]]

Return 4 The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [ [3,4,5], [3,2,6], [2,2,1]]

Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution: DFS to go through all nodes and use another array to cache all the visited node, incase we revisit again. reduce alot of unnecessnary operations. Time complixity is O(nm) .

class Solution { public int longestIncreasingPath(int[][] matrix) { if(matrix.length<=0 || matrix[0].length <=0) return 0; int max=0, n = matrix.length, m = matrix[0].length; int [][] cache = new int[n][m]; for(int i=0;i=matrix.length || c>= matrix[0].length) { return 0; } if(matrix[r][c] <= min) { return 0; } if(cache[r][c] != 0) { return cache[r][c]; } min = matrix[r][c]; int up = maxLen(matrix, min, r-1, c, cache) + 1; int left = maxLen(matrix, min, r, c-1, cache) + 1; int right = maxLen(matrix, min, r, c+1, cache) + 1; int down = maxLen(matrix, min, r+1, c, cache) + 1; cache[r][c] = Math.max(up, Math.max(left, Math.max(right,down))); return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。