剑指 Offer 29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 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]

限制：

• 0 <= matrix.length <= 100
• 0 <= matrix[i].length <= 100

解题思路：此题是寻路算法的前置，在遍历时需要分析寻路时的走向，即先向右，走不通了再向下，走不通了再向左，再走不通了再向上，如此往复，直至矩阵的每一个位置都被访问过。

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return []int{}
    }
    rows, columns := len(matrix), len(matrix[0])
    visited := make([][]bool, rows)
    for i := 0; i < rows; i++ {
        visited[i] = make([]bool, columns)
    }

    var (
        total          = rows * columns
        order          = make([]int, total)
        row, column    = 0, 0
        directions     = [][]int{[]int{0, 1}, []int{1, 0}, []int{0, -1}, []int{-1, 0}}
        directionIndex = 0
    )

    for i := 0; i < total; i++ {
        order[i] = matrix[row][column]
        visited[row][column] = true
        nextRow, nextColumn := row+directions[directionIndex][0], column+directions[directionIndex][1]
        if nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn] {
            directionIndex = (directionIndex + 1) % 4
        }
        row += directions[directionIndex][0]
        column += directions[directionIndex][1]
    }
    return order
}

时间复杂度分析：O(mn)，其中，其中 m 和 n 分别是输入矩阵的行数和列数，矩阵中的每一个元素都要被访问到。

空间复杂度分析：O(mn)，需要新建一个一样大小的 visited 矩阵来记录每个位置是否访问过。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。