54. 螺旋矩阵

题目描述：

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

---

解题分析及思路：

方法一：模拟

首先，我们需要遍历整个矩阵，遍历结束的条件是遍历的元素个数等于矩阵的元素个数。

那么，这个问题的关键是遍历矩阵的时候，如何确定在什么情况下更换方向。

我们可以使用一个二维数组 direction 来表示方向，每次遍历时，根据当前位置是否超出边界或者到达之前遍历的位置，来更换方向。

那么如何判断是否超出边界呢？

• 可以使用directionCount来表示遍历过程中，当拐弯的次数，当遍历到边界时，更换方向，directionCount++。
• 那么，相对应的，该行/列的边界就是 row+direction[index][0]+direction[index][0]*directionCount/4 和 col+direction[index][1]+direction[index][1]*directionCount/4。只需判断是否超出边界即可。

其中：

• row+direction[index][0]表示下一步的行坐标，col+direction[index][1] 表示下一步的列坐标。
• direction[index][0]*directionCount/4 表示当前方向的行坐标的偏移量，direction[index][1]*directionCount/4 表示当前方向的列坐标的偏移量。

所以，整体的逻辑就是按照某个方向不停的遍历，当遍历到边界时，更换方向，直到遍历完所有元素。只需注意边界的判断即可。

var direction = [][]int{
	{0, 1},
	{1, 0},
	{0, -1},
	{-1, 0},
}

func spiralOrder(matrix [][]int) (result []int) {
	rows := len(matrix)
	cols := len(matrix[0])
	var row, col = 0, 0
	var directionCount = 1
	var count = 0
	var index = 0
	for count < rows*cols {
		result = append(result, matrix[row][col])
		count++
		if row+direction[index][0]+direction[index][0]*directionCount/4 < 0 || row+direction[index][0]+direction[index][0]*directionCount/4 >= rows ||
			col+direction[index][1]+direction[index][1]*directionCount/4 < 0 || col+direction[index][1]+direction[index][1]*directionCount/4 >= cols {
			index = (index + 1) % 4
			directionCount++
		}
		row += direction[index][0]
		col += direction[index][1]
	}
	return
}

复杂度：

• 时间复杂度：O(M * N)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:1 ms,击败了25.53% 的Go用户
• 内存消耗:2 MB,击败了21.59% 的Go用户