🔗 螺旋矩阵

题目来源：54. 螺旋矩阵 – 力扣（LeetCode）

---

📌 题目描述

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

• 螺旋顺序：从左上角开始，向右 → 向下 → 向左 → 向上，层层内卷，直到遍历所有元素。
• 返回一个一维列表，包含按此顺序访问的所有元素。

---

✅ 示例解析

示例 1：

• 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
• 输出：[1,2,3,6,9,8,7,4,5]
• 螺旋路径：
  • 向右：1 → 2 → 3
  • 向下：6 → 9
  • 向左：8 → 7
  • 向上：4 → 5（但 5 已访问，实际只到 4，然后 5 在下一层）
    ✅ 实际：[1,2,3] → [6,9] → [8,7] → [4] → [5]？
    更正：实际路径是：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]
• 螺旋路径：
  • 外层：1→2→3→4→8→12→11→10→9→5
  • 内层：6→7
    ✅ 最终：[1,2,3,4,8,12,11,10,9,5,6,7]

---

⚠️ 提示

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

---

💡 解法：四边界模拟法 —— O(mn) 时间，O(1) 额外空间（不计返回值）

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

        int t = 0, b = matrix.length;
        int l = 0, r = matrix[0].length;

        while (t < b && l < r) {
            // 1. 从左到右
            for (int i = l; i < r; i++)
                res.add(matrix[t][i]);
            t++; // 上边界下移

            // 2. 从上到下
            for (int i = t; i < b; i++)
                res.add(matrix[i][r - 1]); // r-1 是当前最右列
            r--; // 右边界左移

            // 3. 从右到左（需检查上边界是否已越过下边界）
            if (t < b) {
                for (int i = r - 1; i >= l; i--)
                    res.add(matrix[b - 1][i]); // b-1 是当前最下行
                b--; // 下边界上移
            }

            // 4. 从下到上（需检查左边界是否已越过右边界）
            if (l < r) {
                for (int i = b - 1; i >= t; i--)
                    res.add(matrix[i][l]);
                l++; // 左边界右移
            }
        }

        return res;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(m × n)
  • 每个元素被访问且仅被访问一次。
  • 总共 m × n 个元素，时间复杂度为线性。
• 空间复杂度：O(1)（不计返回列表）
  • 仅使用常数个变量：t, b, l, r 和循环变量 i。
  • 返回的 res 列表是题目要求的输出，不计入额外空间。

---

🧩 解题思路

1. 核心思想：维护四个边界，模拟螺旋过程
   • 使用四个变量动态表示当前待遍历的矩形区域：
     • t（top）：上边界（行索引）
     • b（bottom）：下边界（行索引），注意是开区间
     • l（left）：左边界（列索引）
     • r（right）：右边界（列索引），注意是开区间
   • 按顺时针顺序：右 → 下 → 左 → 上，每走完一边就收缩对应边界。
2. 四步循环： 步骤 1：从左到右（上边）
   • 遍历列：i 从 l 到 r-1
   • 访问 matrix[t][i]
   • 完成后 t++（上边界下移）
   步骤 2：从上到下（右边）
   • 遍历行：i 从 t 到 b-1
   • 访问 matrix[i][r-1]（最右列）
   • 完成后 r--（右边界左移）
   步骤 3：从右到左（下边）
   • 遍历列：i 从 r-1 到 l（递减）
   • 访问 matrix[b-1][i]（最下行）
   • 关键检查：if (t < b)，防止在单行情况下重复遍历
   • 完成后 b--（下边界上移）
   步骤 4：从下到上（左边）
   • 遍历行：i 从 b-1 到 t（递减）
   • 访问 matrix[i][l]（最左列）
   • 关键检查：if (l < r)，防止在单列情况下重复遍历
   • 完成后 l++（左边界右移）
3. 为什么需要 if (t < b) 和 if (l < r)？
   • 当矩阵的行数或列数为奇数时，最内层可能只剩一行或一列。
   • 例如：[[1,2,3,4]]（单行）
     • 步骤 1 后：t=1, b=1 → t >= b
     • 若不加 if (t < b)，步骤 3 会再次从右到左遍历，导致重复添加 4,3,2,1
   • 因此，必须在步骤 3 和 4 前检查边界是否仍有效。
4. 举例说明：
   对 matrix = [[1,2,3],[4,5,6],[7,8,9]]：
   • 初始：t=0, b=3, l=0, r=3
   • 第1圈：
     • →：1,2,3 → t=1
     • ↓：6,9 → r=2
     • ←：8,7 → b=2（检查 t=1 < b=2 成立）
     • ↑：4 → l=1（检查 l=1 < r=2 成立）
   • 第2圈：
     • →：5 → t=2
     • ↓：无（t=2 >= b=2）
     • ←：跳过（t >= b）
     • ↑：跳过（l >= r）
   • 结束，结果：[1,2,3,6,9,8,7,4,5] ✅