54.螺旋矩阵

模拟

螺旋遍历本质上就是按照右、下、左、上的顺序不断前进，当走到边界时再转向。

因此可以维护当前方向，以及当前还能走的上下左右边界。每次先尝试沿当前方向继续走，如果下一步越界，就说明这一圈对应方向已经走完了，需要切换方向，同时收缩对应边界。之后继续前进并记录答案，直到遍历完全部元素。

时间复杂度 $O(mn)$

空间复杂度 $O(1)$

class Solution {
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] ans = new int[m * n];
        int dir = 3, idx = 0;
        int left = -1, ceil = 0, right = n - 1, floor = m - 1;
        int x = 0, y = -1;
        while (idx < ans.length) {
            int nx = x + DIRS[dir][0];
            int ny = y + DIRS[dir][1];
            if (nx < ceil || ny > right || nx > floor || ny < left) {
                dir = (dir + 1) % 4;
                if (nx < ceil) {
                    left++;
                } else if (ny > right) {
                    ceil++;
                } else if (nx > floor) {
                    right--;
                } else {// ny < left
                    floor--;
                }
            }
            x = x + DIRS[dir][0];
            y = y + DIRS[dir][1];
            ans[idx] = matrix[x][y];
            idx++;
        }
        return Arrays.stream(ans)          // 将int数组转换为IntStream流
            .boxed()                       // 将基本int类型自动装箱为Integer对象
            .collect(Collectors.toList()); // 将流收集到List<Integer>中
    }
}

按层遍历

也可以把矩阵看成一层一层的“环”。

每一轮依次遍历当前最上面一行、最右边一列、最下面一行、最左边一列，然后收缩上下左右四个边界，继续处理下一层。需要注意的是，当矩阵只剩下一行或一列时，要额外判断边界是否仍然有效，避免重复加入元素。

这种写法更直观，也更符合手动模拟螺旋遍历的过程。

时间复杂度 $O(mn)$

空间复杂度 $O(1)$

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) {
                ans.add(matrix[top][i]);
            }
            top++;
            for (int i = top; i <= bottom; i++) {
                ans.add(matrix[i][right]);
            }
            right--;
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    ans.add(matrix[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    ans.add(matrix[i][left]);
                }
                left++;
            }
        }
        return ans;
    }
}