首页>itarticle>leetcode(329) longest increasing path in a matrix 解法:
leetcode(329) longest increasing path in a matrix 解法:
admin11月 29, 20200
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.
publicclass{ publicintlongestIncreasingPath(int[][] matrix){ if (matrix.length == 0) { return0; } int row = matrix.length; int col = matrix[0].length; int max = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int cnt = dfs(i, j, matrix, row, col); if (cnt > max) { max = cnt; } } } return max; }
privateintdfs(int i, int j, int[][] matrix, int row, int col){ Stack s = new Stack(); node start = new node(i, j, matrix[i][j],1); s.push(start); node now = start; int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int cnt = 0; while (!s.isEmpty()) { now = (node) s.pop(); int flag = 0; for (int ii = 0; ii < 4; ii++) { node next = new node(now.i+ direction[ii][0], now.j + direction[ii][1], -1,1); if (isvalid(next, row, col) && matrix[next.i][next.j] > now.value) { next.value = matrix[next.i][next.j]; next.step = now.step + 1; s.push(next); flag = 1; } } if(flag == 0){ if(now.step > cnt){ cnt = now.step; } } } return cnt; }
privatebooleanisvalid(node n, int row, int col){ if (n.i >= 0 && n.i < row && n.j >= 0 && n.j < col ) { returntrue; } returnfalse; }
}
classnode{ int i; int j; int value; int step = 1;
node(int i, int j, int value,int step) { this.i = i; this.j = j; this.value = value; this.step = step; } }
publicclass{ publicintlongestIncreasingPath(int[][] matrix){ if (matrix.length == 0) { return0; } int row = matrix.length; int col = matrix[0].length; int memory[][] = newint[row][col]; int max = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int cnt = dfs(i, j, matrix, row, col,memory); if (cnt > max) { max = cnt; } } } return max; }
privateintdfs(int i, int j, int[][] matrix, int row, int col,int[][] memory){ int maxstep = 1; if(memory[i][j]>0){ return memory[i][j]; } node now = new node(i,j,matrix[i][j],0); int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int ii = 0; ii < 4; ii++){ node next = new node(now.i+ direction[ii][0], now.j + direction[ii][1], -1,1); if (isvalid(next, row, col) && matrix[next.i][next.j] > now.value){ next.value = matrix[next.i][next.j]; int cal = dfs(next.i,next.j,matrix,row,col,memory) + 1; if(maxstep < cal){ maxstep = cal; } } } memory[i][j] = maxstep; return memory[i][j]; }
privatebooleanisvalid(node n, int row, int col){ if (n.i >= 0 && n.i < row && n.j >= 0 && n.j < col ) { returntrue; } returnfalse; }
}
classnode{ int i; int j; int value; int step = 1;
node(int i, int j, int value,int step) { this.i = i; this.j = j; this.value = value; this.step = step; } }
近期评论