矩阵-54. 螺旋矩阵

文章目录一、核心解题思路1. 核心思想边界收缩法模拟顺时针遍历2. 时间 / 空间复杂度二、完整 Java 代码符合大厂机考标准含控制台输入输出三、注意★★★边界判断的必要性力扣地址 中等54. 螺旋矩阵挺简单的一、核心解题思路1. 核心思想边界收缩法模拟顺时针遍历这道题的本质是模拟顺时针螺旋遍历矩阵的过程通过定义四个边界来控制遍历范围每遍历完一条边就收缩对应边界直到所有元素遍历完成。四个边界定义left当前遍历的左边界列索引right当前遍历的右边界列索引top当前遍历的上边界行索引bottom当前遍历的下边界行索引遍历顺序顺时针从左到右遍历上边界top行从left列到right列遍历完成后上边界top收缩上边界从上到下遍历右边界right列从top行到bottom行遍历完成后右边界right--收缩右边界从右到左遍历下边界bottom行从right列到left列遍历完成后下边界bottom--收缩下边界从下到上遍历左边界left列从bottom行到top行遍历完成后左边界left收缩左边界关键边界判断每完成一条边的遍历后必须判断边界是否越界比如top bottom或left right如果越界说明所有元素已经遍历完成直接终止循环避免重复遍历。2. 时间 / 空间复杂度时间复杂度O(m×n)矩阵中每个元素仅被访问一次空间复杂度O(1)除结果数组外仅使用常数额外空间classSolution{publicListIntegerspiralOrder(int[][]matrix){intleft0,rightmatrix[0].length-1,top0,bottommatrix.length-1;ListIntegerresnewArrayList();while(leftrighttopbottom){for(intileft;iright;i){res.add(matrix[top][i]);}top;if(topbottom)break;for(intitop;ibottom;i){res.add(matrix[i][right]);}right--;if(leftright)break;for(intiright;ileft;i--){res.add(matrix[bottom][i]);}bottom--;if(topbottom)break;for(intibottom;itop;i--){res.add(matrix[i][left]);}left;if(leftright)break;}returnres;}}二、完整 Java 代码符合大厂机考标准含控制台输入输出importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassMain{publicstaticListIntegerspiralOrder(int[][]matrix){// 定义四个边界intleft0;intrightmatrix[0].length-1;inttop0;intbottommatrix.length-1;ListIntegerresnewArrayList();while(leftrighttopbottom){// 1. 从左到右遍历上边界for(intileft;iright;i){res.add(matrix[top][i]);}top;// 上边界收缩if(topbottom)break;// 边界越界终止// 2. 从上到下遍历右边界for(intitop;ibottom;i){res.add(matrix[i][right]);}right--;// 右边界收缩if(leftright)break;// 边界越界终止// 3. 从右到左遍历下边界for(intiright;ileft;i--){res.add(matrix[bottom][i]);}bottom--;// 下边界收缩if(topbottom)break;// 边界越界终止// 4. 从下到上遍历左边界for(intibottom;itop;i--){res.add(matrix[i][left]);}left;// 左边界收缩if(leftright)break;// 边界越界终止}returnres;}publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);intmscanner.nextInt();intnscanner.nextInt();int[][]matrixnewint[m][n];for(inti0;im;i){for(intj0;jn;j){matrix[i][j]scanner.nextInt();}}System.out.println(spiralOrder(matrix));}}三、注意★★★边界判断的必要性如果没有边界判断会出现重复遍历的问题比如只有一行的矩阵[[1,2,3,4]]第一步遍历完上边界后top1此时top bottombottom0如果不 break会继续执行后续遍历导致重复访问元素比如只有一列的矩阵[[1],[2],[3],[4]]第二步遍历完右边界后right-1此时left right如果不 break会继续执行后续遍历导致重复访问元素