题目描述#

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

这题的关键不在于怎么“转弯”，而在于如何在不断缩小的边界里，按固定顺序把每一圈完整走完，并且避免重复访问。

思路#

这份解法用四个边界来描述当前还没有遍历过的矩形区域：left、right、top、bottom。一开始它们分别指向最左列、最右列、最上行和最下行。只要当前区域还存在，也就是 left <= right && top <= bottom，就可以继续按一圈一圈的方式遍历。

每一圈都固定分成四步。第一步从左到右遍历最上面一行，走完后把 top 下移一格，表示这一行已经处理过。第二步从上到下遍历最右边一列，走完后把 right 左移一格。第三步从右到左遍历最下面一行，第四步从下到上遍历最左边一列。这样就完成了一整圈。

需要注意的是，后两步不是每次都能直接执行。比如只剩下一行时，完成“向右”之后，top 可能已经大于 bottom，这时候如果还继续“向左”就会重复遍历。同理，只剩下一列时，也要避免继续“向上”。所以代码里在“向左”前判断 top <= bottom，在“向上”前判断 left <= right，这两个判断就是为了处理单行、单列这样的边界情况。

整个过程中，每访问一个元素就加入答案数组，四个边界不断向中间收缩，直到没有剩余区域为止。时间复杂度是 O(m*n)，因为每个元素只会被访问一次；额外空间复杂度是 O(1)，不算返回结果的话只用了几个边界变量。

代码#

func spiralOrder(matrix [][]int) (ans []int) {
	left, right := 0, len(matrix[0])-1
	top, bottom := 0, len(matrix)-1

	for left <= right && top <= bottom {
		// 向右
		for i := left; i <= right; i++ {
			ans = append(ans, matrix[top][i])
		}
		top++
		// 向下
		for i := top; i <= bottom; i++ {
			ans = append(ans, matrix[i][right])
		}
		right--
		// 向左
		if top <= bottom {
			for i := right; i >= left; i-- {
				ans = append(ans, matrix[bottom][i])
			}
			bottom--
		}
		// 向上
		if left <= right {
			for i := bottom; i >= top; i-- {
				ans = append(ans, matrix[i][left])
			}
			left++
		}
	}
	return
}