【数组篇】day20_54. 螺旋矩阵

题解：

思路：

• 定义一个与原数组一样大小的数组，用于标记元素是否访问

• 按照题意可知，顺时针螺旋顺序 访问数组，元素依次向 右->下->左->上 方向移动

复杂度：

• 时间复杂度：O(mn) 
• 空间复杂度：O(mn) 

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        // 标记元素是否访问
        boolean[][] visited = new boolean[m][n];

        // 坐标位移方向 右->下->左->上
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        // 元素总数
        int total = m * n;
        int row = 0, column = 0;
        int dirIndex = 0;
        for (int i = 0; i < total; i++) {
            res.add(matrix[row][column]);
            visited[row][column] = true;

            // 下一个元素的坐标
            int nextRow = row + dirs[dirIndex][0], nextColumn = column + dirs[dirIndex][1];
            // 判断是否越界
            if (nextRow < 0 || nextRow >= m || nextColumn < 0 || nextColumn >= n || visited[nextRow][nextColumn]) {
                // 改变位移方向
                dirIndex = (dirIndex + 1) % 4;
            }

            row += dirs[dirIndex][0];
            column += dirs[dirIndex][1];
        }
        return res;
    }
}