🔗 旋转图像

题目来源：48. 旋转图像 – 力扣（LeetCode）

---

📌 题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

• 要求：
  • 必须在 原地 修改输入矩阵（即不能使用另一个矩阵来辅助旋转）。
  • 旋转后，原矩阵应被直接修改为旋转后的结果。

---

✅ 示例解析

示例 1：

• 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
• 输出：[[7,4,1],[8,5,2],[9,6,3]]
• 解释：
  • 原矩阵：深色版本1 2 3 4 5 6 7 8 9
  • 顺时针旋转 90° 后：深色版本7 4 1 8 5 2 9 6 3

示例 2：

• 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
• 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
• 解释：这是一个 4×4 矩阵，旋转后外层和内层元素均按顺时针方向移动。

---

⚠️ 提示

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

---

💡 解法：分层旋转（环形替换）—— O(n²) 时间，O(1) 额外空间

class Solution {
    public void rotate(int[][] matrix) {
        int left = 0, right = matrix[0].length - 1;
        while (left < right) {
            for (int i = 0; i < right - left; i++) {
                int top = left, bottom = right;
                // 保存左上角的元素
                int p = matrix[top][left + i];
                
                // 逆时针四步替换（等效于顺时针旋转）
                matrix[top][left + i] = matrix[bottom - i][left];           // 左下 → 左上
                matrix[bottom - i][left] = matrix[bottom][right - i];       // 右下 → 左下
                matrix[bottom][right - i] = matrix[top + i][right];         // 右上 → 右下
                matrix[top + i][right] = p;                                 // 左上 → 右上
            }
            left++;
            right--;
        }
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n²)
  • 外层 while 循环执行 n/2 次（每层一圈）
  • 内层 for 循环遍历当前圈的边长减一（right - left）
  • 总体访问了矩阵中几乎每个元素一次，为 O(n²)
• 空间复杂度：O(1) ✅
  • 仅使用常数个额外变量：left, right, top, bottom, i, p
  • 所有操作均在原矩阵上进行，完全原地修改，满足题目要求。

---

🧩 解题思路

1. 核心思想：分层旋转 + 四点环形替换
   • 将 n×n 矩阵视为多个“同心方框”（从外到内）。
   • 对每一层（每一圈），将四个边上的对应元素进行顺时针旋转。
   • 通过一次保存 + 三次赋值完成四个位置的元素轮换。
2. 关键变量定义：
   • left, right：当前层的左右边界列索引
   • top, bottom：当前层的上下边界行索引（top = left, bottom = right，因为是方阵）
   • i：在当前边上移动的偏移量，用于遍历该层的一条边。
3. 四步替换过程（顺时针旋转）：
   对于当前层的一个“四元组”（左上、右上、右下、左下），进行如下替换：
   1. 保存左上角元素 p = matrix[top][left + i]
   2. 左下 → 左上：matrix[top][left + i] = matrix[bottom - i][left]
   3. 右下 → 左下：matrix[bottom - i][left] = matrix[bottom][right - i]
   4. 右上 → 右下：matrix[bottom][right - i] = matrix[top + i][right]
   5. 左上（p）→ 右上：matrix[top + i][right] = p
   这相当于：深色版本左上 ← 左下 ← 右下 ← 右上 ← (左上)
4. 为什么是 right - left 次循环？
   • 当前层的边长为 len = right - left + 1
   • 每次旋转处理一个“四元组”，但每条边只需要处理前 len - 1 个元素（最后一个会被下一个四元组或上一轮覆盖）
   • 因此内层循环次数为 right - left（即 len - 1）
5. 举例说明：
   对 matrix = [[1,2,3],[4,5,6],[7,8,9]]：
   • 第1层（外层）：left=0, right=2
     • i=0：
       • 保存 p = matrix[0][0] = 1
       • matrix[0][0] = matrix[2][0] = 7
       • matrix[2][0] = matrix[2][2] = 9
       • matrix[2][2] = matrix[0][2] = 3
       • matrix[0][2] = p = 1
     • i=1：对 i=1 位置进行类似操作
   • 结束后 left=1, right=1，循环结束
   • 最终得到 [[7,4,1],[8,5,2],[9,6,3]] ✅
6. 边界处理：
   • 单元素中心（n 为奇数）：left == right 时停止，中心元素无需旋转。
   • 双元素层（n 为偶数）：最后一层 right - left = 1，循环一次即可。