Problem
1. 题目简述
给出一个m * n的矩阵，将其螺旋打印出来。例如：
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
2. 算法思路
相关问题：
极其经典的螺旋打印的问题，这里的暴力做法其实是很麻烦的，用方向数组比较好！
暴力解法——螺旋打印
注意这里的边界情况是只有一行或者一列的情况，要特殊处理，比较麻烦，建议直接去看第二写法或者解法二。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
// 每次打印一圈，直至index越界直接return，写一个子函数。
List<Integer> res = new ArrayList();
helper(matrix, 0, 0, res);
return res;
}
private void helper (int[][] matrix, int i, int j, List<Integer> res) {
if (matrix.length == 0) {
return;
}
int m = matrix.length, n = matrix[0].length;
int height = m - 2 * i, width = n - 2 * j;
// 越界的情况
if (width <= 0 || height <= 0) {
return;
}
// 剩下一行或一列的情况
if (height == 1) {
// 一行
for (int x = 0; x < width; x++) {
res.add(matrix[i][j + x]);
}
return;
}
if (width == 1) {
// 一列
for (int x = 0; x < height; x++) {
res.add(matrix[i + x][j]);
}
return;
}
// 开始按圈添加res
// 上方一行，例如[1,2]
for (int x = 0; x < width - 1; x++) {
res.add(matrix[i][j + x]);
}
// 右侧一列，例如[3,6]
for (int x = 0; x < height - 1; x++) {
res.add(matrix[i + x][j + width - 1]);
}
// 下方一行，例如[9,8]
for (int x = 0; x < width - 1; x++) {
res.add(matrix[i + height - 1][j + width - 1 - x]);
}
// 左侧一列，例如[7, 4]
for (int x = 0; x < height - 1; x++) {
res.add(matrix[i + height - 1 - x][j]);
}
helper(matrix, i + 1, j + 1, res);
}
}第二种写法和下面的解法二有异曲同工之妙，最好记一下，这样不需要去使用额外的m*n的空间，也就是isVisited数组。题解链接：题解
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0) return new int[0];
int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
int[] res = new int[(r + 1) * (b + 1)];
while(true) {
for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
if(++t > b) break;
for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
if(l > --r) break;
for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
if(t > --b) break;
for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
if(++l > r) break;
}
return res;
}
}方向数组巧妙解法
对于这种需要四个方向dfs的题目来说，方向数组最适合不过了，对于四个方向，只需要定义dx和dy即可。也就是说dx = [-1, 1, 0, 0]， dy = [0, 0, -1, 1]，分别对应“上下左右”四个方向，每次只需要判断是否越界或者已经填充即可。这么写的好处是节省脑力，不需要判断每次的长度，很省事！！！但是相应的有一丢丢浪费空间，因为需要额外的bool数组来存储每个数字是否已经打印。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
if (matrix.length == 0) {
return new ArrayList<Integer>();
}
int m = matrix.length, n = matrix[0].length;
// 这里用一个boolean数组来定义是否已经访问过该数字
boolean[][] isVisited = new boolean[m][n];
// 定义四个方向，此题的顺序应该是右下左上，注意顺序
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
// 定义一个返回的结果集
List<Integer> res = new ArrayList();
int x = 0, y = 0, direction = 0;
while (res.size() < m * n) {
res.add(matrix[x][y]);
isVisited[x][y] = true;
if (x + dx[direction] < 0 || x + dx[direction] >= m || y + dy[direction] < 0 || y + dy[direction] >= n || isVisited[x + dx[direction]][y + dy[direction]] == true) {
// 此时需要变更方向
direction = (direction + 1) % 4;
}
x += dx[direction];
y += dy[direction];
}
return res;
}
}