498. 对角线遍历
根据题目的图像看,主要有两种走法,第一种是向右上(顺时针方向),第二种是向左下(逆时针)走
我们设 x ,y初始为0,分别对应横纵坐标
-
现在分析右上(0,2) 为例:(注意右上的判断方向是顺时针 右上-->右-->下)
-
先判断是否可以右上 (5-->3),可以右上,则移动,并且下一个坐标继续判断是否可以右上
-
不可以右上,则判断是否可以向右(1-->2),可以向右,则移动,并且下一个坐标需要换方向(左下)
-
不可向右,再判断是否可以向下 (3-->6),可以向下,则移动,并且下一个坐标需要换方向(左下)
-
-
现在分析左下上(2,1) 为例:(注意左下的判断方向是逆时针,左下-->下-->右)
- 先判断是否可以左下 (2-->4),可以左下,则移动,并且下一个坐标继续判断是否可以左下
- 不可以左下,则判断是否可以向下(4-->7),可以向下,则移动,并且下一个坐标需要换方向(右上)
- 不可向下,再判断是否可以向右 (8-->9),可以向右,则移动,并且下一个坐标需要换方向(右上)
-
代码
class Solution { public static int[] findDiagonalOrder(int[][] matrix) { if(matrix.length==0){ return new int[0]; } int row = matrix.length-1;//行 int col = matrix[0].length-1;//列 int len = (row+1)*(col+1); int[] res = new int[len];//结果数组 int index = 0;//结果数组的存储下标 int x = 0;//对应row int y = 0;//对应col res[index] = matrix[x][y]; while(x!=row || y!= col){ //先右上 while (true) { if(x==row && y== col){ break; } if (x - 1 >= 0 && y + 1 <= col) { //可以右上 index++; res[index] = matrix[--x][++y]; } else { //不可以右上,看看能不能右移 if (y + 1 <= col) { index++; res[index] = matrix[x][++y]; break; } //看看能不能下移 if (x+1 <= row) { index++; res[index] = matrix[++x][y]; break; } } } while (true) { if(x==row && y== col){ break; } //再左下 if (y - 1 >= 0 && x + 1 <= row) { //可以左下 index++; res[index] = matrix[++x][--y]; } else { //看看能不能下移 if (x+1 <= row) { index++; res[index] = matrix[++x][y]; break; } //不可以左下,看看能不能右移 if (y + 1 <= col) { index++; res[index] = matrix[x][++y]; break; } } } } return res; } }