【LeetCode 热题 100】54. 螺旋矩阵

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

整体思路

这段代码旨在解决一个经典的矩阵问题：螺旋矩阵 (Spiral Matrix)。问题要求按照顺时针螺旋的顺序，返回矩阵中的所有元素。

该算法采用了一种非常直观的 “路径模拟” 策略。它模拟一个“机器人”在矩阵中行走，并根据边界和已访问过的路径来决定何时转向。

其核心逻辑步骤如下：

1. 状态与方向定义：

   • 算法使用 (i, j) 来追踪当前在矩阵中的位置。
   • 一个静态常量数组 DIRS {{0, 1}, {1, 0}, {0, -1}, {-1, 0}} 被用来定义四个方向：右、下、左、上。
   • 一个方向索引 di (0到3) 被用来表示当前的行进方向。

2. 遍历与标记：

   • 算法的核心是一个 for 循环，它会精确地执行 m * n 次，确保矩阵中的每一个元素都被访问一次。
   • 在每次循环中，首先将当前位置 matrix[i][j] 的值添加到结果列表 ans 中。
   • 关键技巧：为了记录已经访问过的位置，算法并未使用一个额外的 boolean[][] visited 数组，而是直接 修改原矩阵。它将访问过的元素 matrix[i][j] 的值设置为一个特殊的标记值 Integer.MAX_VALUE。这是一种在允许修改输入的情况下，节省空间的常用方法。

3. 转向逻辑 (Collision Detection)：

   • 在每次移动之前，算法会进行一次“预判”或“向前看”。
   • 它根据当前的方向 di，计算出下一步将要到达的坐标 (x, y)。
   • 然后，它检查这个下一步是否有效。无效的条件有两种：
     a. 越界：下一步的坐标 (x, y) 超出了矩阵的边界（x < 0, x >= m, y < 0, or y >= n）。
     b. 已访问：下一步的坐标 (x, y) 上的值等于标记值 Integer.MAX_VALUE，说明这个位置已经被访问过。
   • 如果下一步无效，就需要转向。转向操作通过 di = (di + 1) % 4 实现，这会让方向索引在 0, 1, 2, 3 之间循环切换。

4. 移动：

   • 在确定了正确的方向（可能是原方向，也可能是转向后的新方向）之后，算法更新当前的位置 (i, j)，使其向新方向移动一步。
   • 这个过程不断重复，直到所有 m * n 个元素都被访问完毕。

完整代码

class Solution {
    // 定义四个方向：右, 下, 左, 上
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    /**
     * 按照顺时针螺旋顺序返回矩阵中的所有元素。
     * @param matrix 一个 M x N 的整数矩阵
     * @return 包含螺旋顺序元素的列表
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 预分配容量，提高性能
        List<Integer> ans = new ArrayList<>(m * n);
        
        // i, j: 当前在矩阵中的坐标
        int i = 0;
        int j = 0;
        // di: 当前方向在 DIRS 数组中的索引，0代表向右
        int di = 0;
        
        // 循环 m * n 次，确保访问每一个元素
        for (int k = 0; k < m * n; k++) {
            // 将当前元素添加到结果列表中
            ans.add(matrix[i][j]);
            // 关键技巧：原地修改矩阵，将访问过的位置标记为一个特殊值
            matrix[i][j] = Integer.MAX_VALUE;
            
            // 预判下一步的坐标
            int x = i + DIRS[di][0];
            int y = j + DIRS[di][1];
            
            // 转向逻辑：如果下一步越界或已访问，则改变方向
            if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == Integer.MAX_VALUE) {
                // (di + 1) % 4 实现方向的循环切换 (右->下->左->上->右)
                di = (di + 1) % 4;
            }
            
            // 根据最终确定的方向（可能是新方向），更新当前坐标
            i += DIRS[di][0];
            j += DIRS[di][1];
        }
        
        return ans;
    }
}

时空复杂度

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

1. 主循环：算法的核心是一个 for 循环，它精确地执行 M * N 次，其中 M 和 N 是矩阵的行数和列数。
2. 循环内部操作：在循环的每一次迭代中，执行的操作（ans.add、数组读写、加法、比较）都是常数时间复杂度的，即 O(1)。

综合分析：
算法的总时间复杂度是循环次数乘以循环体内部的复杂度，即 (M * N) * O(1)。因此，总的时间复杂度为 O(M * N)。

空间复杂度：O(1) (不考虑输出列表)

1. 主要存储开销：
   • List<Integer> ans：这个列表用于存储最终的输出结果。其大小为 M * N。按照惯例，返回结果所需的空间不计入额外辅助空间。
   • DIRS：这是一个静态常量数组，其大小固定为 4x2，不随输入规模变化，因此是 O(1)。
   • 原地修改：该算法通过修改输入矩阵 matrix 来标记已访问的单元格，避免了创建一个与矩阵等大的 boolean[][] visited 辅助数组。
2. 辅助变量：m, n, i, j, di, k, x, y 等都是常数数量的原始类型变量，占用 O(1) 空间。

综合分析：
如果不考虑为存储输出结果而分配的空间，该算法只使用了常数级别的额外空间。因此，其辅助空间复杂度为 O(1)。这是一个空间效率非常高的解法（前提是允许修改输入矩阵）。

参考灵神