描述

给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

数据范围：0≤ n,m ≤10，矩阵中任意元素都满足 ∣val∣≤100

要求：空间复杂度 O(nm)，时间复杂度 O(nm)

示例1

输入：

[[1,2,3],[4,5,6],[7,8,9]]

返回值：

[1,2,3,6,9,8,7,4,5]

示例2

输入：

[]

返回值：

[]

做题

又是一道只能遍历解决的题，个人感觉做这种提不需要太多的数学知识，对新手来说还是比较友好的。

这道题目的意思就是希望我们能够顺时针地螺旋地去遍历一个数组，我试想了一下，貌似不太可能一个循环就做完，必须在一个大的循环下面再包含四个小的循环去遍历正方形的边。

* 1 2 3
* 4 5 6
* 7 8 9

把要螺旋展示的数组分成一圈一圈的，先螺旋遍历外圈，再到内圈，呈一个往内缩的趋势。

也就是先 1-2-3-6-9-8-7-4，再到 5。

那这个外圈怎么遍历呢 ？

我们要有一个坐标(x,y)，我们先遍历上边框：1-2-3；然后再遍历右边框：6，这里就不到 9 了；

遍历下边框：9-8-7 ，最后就是左边框：4

图片稍微有点“精致”，不要在意。

我们需要把上下左右边框的边界都用一个变量存储起来，比如 3*3 数组的第一层外边框，
top(0) 和 bottom(2) 分别定位第一行和第三行，这两行就是前者向右遍历，后者先左遍历， left < x < right，y = top/bottom

left(0) 和 right(2) 分别定位第一列和第三列，前者向上遍历，后者向下遍历，top < y < bottom，x = left/right

在完成边框循环之后就全部 ++/–，收缩边界

那么到最内层之后就会出现两种情况，要么是一个完好的正方形，要么是只有一个数，像上图中的例子，中间只有一个 9，下图的例子，中间就会有一个紧挨着的正方形。

那这两种情况该怎么兼容呢？

为了兼容这两种情况，上边框以及下边框都是一次性遍历完，也就是 1-0-1-2 和 5-6-7-2 一次性遍历完，左右边框就只遍历中间部分，不包括开头和结尾。

还有循环边界问题，我们需要找到最后一个内边框，也就是当什么情况下，我们就是已经遍历了最后一个边框。

* 1 2
* 3 4

我们拿一个二阶数组来求循环的边界。

这时的 top(0),bottom(1),left(0),right(1)。

当循环完一圈之后，边界内缩：top++,bottom–,right–,left++。

top(1),bottom(0),left(1),right(0)

也就是当 top < bottom 或者 left > right 时就要停止循环。

大概的思路就是这样，具体的就敲代码遇到再解决。

代码

public ArrayList<Integer> spiralOrder(int[][] matrix) {ArrayList<Integer> result = new ArrayList<Integer>();if (matrix.length == 0 || matrix[0].length == 0) {return result;}//上下左右边界int top = 0, bottom = matrix.length - 1;int left = 0, right = matrix[0].length - 1;//坐标int x = 0, y = 0;while (top <= bottom && left<=right) {for (x = left - 1, y = top; x < right; ) {//往右移动x++;result.add(matrix[y][x]);}/**为了解决奇数组少一个数和偶数组多一个数的问题* 这里在遍历上边框时，直接遍历到了 right*/for (x = right, y = top + 1; y < bottom; y++) {///往下移动result.add(matrix[y][x]);}/*** 因为还存在一维数组，就是像 {{1,2,3,4}} 和 {{1},{2},{3},{4}} 这样的* 所以当 top == bottom 和 left == right 时，就是这种一维数组，这样的话，下边框和左边框就不需要再遍历了*/for (x = right+1, y = bottom; top != bottom && x > left; ) {x--;//向左移动result.add(matrix[y][x]);}for (x = left, y = bottom-1; left != right && y > top; y--) {//向上移动result.add(matrix[y][x]);}//收缩边界top++;bottom--;right--;left++;}return result;
}

运行！

最后

这是牛客上最后一道入门级别的算法题了，我个人感觉做下来还是有点吃力，看来算法道路还很长，加油。

今天的算法就到这里了。

这里是程序员徐小白，【每日算法】是我新开的一个专栏，在这里主要记录我学习算法的日常，也希望我能够坚持每日学习算法，不知道这样的文章风格您是否喜欢，不要吝啬您免费的赞，您的点赞、收藏以及评论都是我下班后坚持更文的动力。