leetcode-go/矩阵/20-旋转图像.md

tags, create time

tags	create time
LeetCode 矩阵 中等	2026-05-17 15:00

20-旋转图像

题面

LeetCode 48. Rotate Image

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

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[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]]

提示：

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

---

思路

[!question] 💡 动手试试：把一张纸顺时针转 90°，原来在左上角的元素会去哪？

直观地想，如果把手机顺时针翻转 90°：

• 原来的第一行 [1, 2, 3] 变成了最后一列（从下到上）
• 原来的最后一行 [7, 8, 9] 变成了第一列（从上到下）

更精确地说——位置 (i, j) 的元素，旋转后会去往新位置 (j, n-1-i)。

原始位置	旋转后位置
(0, 0)	(0, 2)
(0, 1)	(1, 2)
(0, 2)	(2, 2)
(1, 0)	(0, 1)
(1, 1)	(1, 1) ← 中心不动
(2, 0)	(0, 0)
(2, 1)	(1, 0)
(2, 2)	(2, 0)

但直接用这个公式逐个搬运会很麻烦——因为你无法确定哪个是"已处理过的旧值"，会导致数据覆盖丢失。我们需要找一个成对交换、自包含的操作模式。

---

方法一：分层模拟法 —— 逐层旋转（O(1) 空间）⭐⭐⭐

[!question] 💡 分解问题：n×n 矩阵可以看作多少个嵌套的「边框」？

以 4×4 为例，想象一个俄罗斯套娃：

flowchart TD
    A["4×4 矩阵"] --> B["第 0 层：最外层边框 12 个元素参与旋转"]
    B --> C["第 1 层：内层 2×2 边框 4 个元素参与旋转"]
    C --> D(["完成"])

    style A fill:#e1f5fe
    style B fill:#fff3e0
    style C fill:#f3e5f5
    style D fill:#e8f5e9

每一层的四个边上，对应位置的四个元素互相轮换：

   A → B
   ↓   ↓
   D ← C

轮换关系：A→B→C→D→A （顺时针移动）

[!abstract] 🗺️ 核心观察：四个角组成一个循环

对于第 layer 层（从外往里数），遍历该层的每一条边（但不包括最后一个点，因为那是第四个角，会被自动补齐）。每次取一条边上相邻的四个对应位置：

                    (layer, j)                     → 顶部
                        ↓                            |
                (n-1-j, layer)                      | 左侧
                        ↑                            |
                        |                            ↓
                    (n-1-layer, n-1-j)          → 底部

                    ↻ 顺时针四向互换

具体映射：设当前在第 layer 层的第 offset 个位置：

角色	坐标	含义
上	(layer, layer + offset)	上边
右	(layer + offset, n - 1 - layer)	右边
下	(n - 1 - layer, n - 1 - layer - offset)	下边
左	(n - 1 - layer - offset, layer)	左边

四个位置的值做环形交换：top → right → bottom → left → top

[!step] 算法流程

flowchart TB
    Start(["开始"]) --> InitLayers["① layer = 0, 最外层"]
    InitLayers --> CountOffset["② 每层 offset 范围：0 ~ (n-1-2*layer)-1"]
    CountOffset --> QuadLoop["③ 对每个 offset，取四对元素做环形交换"]
    QuadLoop --> NextLayer{"layer++ < n/2?"}
    NextLayer -->|"是"| InitLayers
    NextLayer -->|"否"| Return(["返回结果"])

1. 外层循环：layer 从 0 到 n/2 - 1（共有 ⌊n/2⌋ 层）
2. 内层循环：offset 从 0 到 (n - 1 - 2*layer) - 1
3. 每个 (layer, offset) 找到四个对应位置，用临时变量做 3 次 swap 完成环形交换

[!example] 🔍 逐步跟踪演示

以 3×3 矩阵为例：

[[1, 2, 3],     layer=0
 [4, 5, 6],     n = 3, n/2 = 1, 只有 1 层
 [7, 8, 9]]

layer = 0, offset = 0:

• 上: (0, 0) = 1
• 右: (0, 2) = 3
• 下: (2, 2) = 9
• 左: (2, 0) = 7

四向交换：1→右, 3→下, 9→左, 7→上 → 上得 7, 右得 1, 下得 3, 左得 9

[[7, 2, 1],
 [4, 5, 6],
 [9, 8, 3]]

layer = 0, offset = 1:

• 上: (0, 1) = 2
• 右: (1, 2) = 6
• 下: (2, 1) = 8
• 左: (2, 0) = 9 — 等等，(2,0) 已经被改成了 9...

让我重新理清：我们用临时变量暂存，而不是连续写入同一个位置：

temp = 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] = temp = 1                    // 上→右

得到：

[[7, 2, 1],
 [4, 5, 6],
 [9, 8, 3]]

layer = 0, offset = 1:

• 上: (0, 1) = 2
• 右: (1, 2) = 6
• 下: (2, 1) = 8
• 左: (1, 0) = 4

temp = 2, matrix[0][1] = 4, matrix[1][0] = 8, matrix[1][2] = 2, matrix[2][1] = 6

得到：

[[7, 4, 1],
 [8, 5, 2],
 [9, 6, 3]]

完成！✅

[!note] 📌 复杂度分析

维度	复杂度	说明
时间	O(n²)	共 n²/2 个需要移动的元素，每个常数次操作
空间	O(1)	只用一个临时变量 temp

[!quote] ❌ 评价

这种方法直接模拟题目要求，逻辑清晰且最优。但在实现时需要仔细推导四个方向的坐标公式，容易出错。面试中如果时间充裕可以尝试，但需要足够的耐心调试坐标。

---

方法二：先转置再翻转 —— 两步操作法 ⭐⭐⭐（推荐）

[!question] 💡 还记得我们之前讨论的矩阵转置吗？转置是把行列互换，那转置后再做些调整，能不能凑出旋转效果？

这是面试中最推荐的解法，因为它把旋转拆解为两个极其简单的子问题：

[!abstract] 🎯 核心洞察

旋转 90° = 沿主对角线转置 + 左右翻转每行

让我们验证一下：

原始矩阵        转置后           每行左右翻转
[[1,2,3]]      [[1,4,7]]       [[7,4,1]]
[[4,5,6]]  →    [[2,5,8]]  →    [[8,5,2]]
[[7,8,9]]      [[3,6,9]]       [[9,6,3]]

与目标输出一致 ✅

[!question] 💡 为什么会这样？从几何角度理解

flowchart LR
    A["原始矩阵<br/>按左上↘右下对角线对称"] --> B["转置：<br/>row↔col 互换"]
    B --> C["左右翻转<br/>每行的首尾对调"]
    C --> D["顺时针旋转 90°"]

    style A fill:#e1f5fe
    style B fill:#fff3e0
    style C fill:#f3e5f5
    style D fill:#e8f5e9

直觉解释：

1. 转置相当于沿对角线折叠翻折（mirror across main diagonal）
2. 左右翻转相当于垂直轴镜像（mirror across vertical midline）
3. 两次镜像 = 一次旋转（在二维空间中，两次正交反射等价于旋转 180° 的一部分；这里是 90°，因为两条镜面夹角为 45°）

[!tip] 变体记忆法

如果你想不起来是"先转置再左右翻转"还是"先上下翻转再左右转置"，记住：

变换组合	结果
转置 + 左右翻转	顺时针旋转 90°
转置 + 上下翻转	逆时针旋转 90°
上下翻转 + 左右转置	顺时针旋转 90°

只要记住一组就够了，另一组作为验证。

[!step] 算法流程

Step ①：转置（Transpose）

遍历主对角线上方的所有元素 (i, j)（其中 i < j），交换 matrix[i][j] 和 matrix[j][i]：

for i := 0; i < n; i++ {
    for j := i + 1; j < n; j++ {
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    }
}

注意这里只需要遍历 j > i 的区域（上三角），避免重复交换回去。

Step ②：每行左右翻转（Reverse Each Row）

for i := 0; i < n; i++ {
    for j := 0; j < n/2; j++ {
        matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
    }
}

每行只需翻转一半长度。

flowchart TB
    Start(["开始"]) --> Transpose["① 沿主对角线转置<br/>遍历上三角区域 i<j"]
    Transpose --> ReverseRows["② 每行左右翻转<br/>头尾配对交换"]
    ReverseRows --> Return(["返回结果"])

[!note] 📌 复杂度分析

维度	复杂度	说明
时间	O(n²)	转置 O(n²/2) + 翻转 O(n²/2)，总计 O(n²)
空间	O(1)	仅用交换时的临时变量

[!success] ✅ 为什么推荐这个方法？

• 代码极其简洁——每步都只有一个双循环，不易出错
• 易验证正确性——可以单独测试转置和翻转的正确性
• 面试友好——可以先写出转置，再引导面试官推导出"加上翻转就完成了"
• 扩展性强——同样的思路可以推广到旋转 180°（两次转置=不变，所以需要两次翻转）、逆时针 90°（转置+上下翻转）等变体

---

代码提示

[!abstract] 📝 伪代码框架（先转置再翻转）

// ── Step 1: 沿主对角线转置 ──
for i 从 0 到 n-1:
    for j 从 i+1 到 n-1:
        交换 matrix[i][j] 和 matrix[j][i]

// ── Step 2: 每行左右翻转 ──
for i 从 0 到 n-1:
    for j 从 0 到 n/2-1:
        交换 matrix[i][j] 和 matrix[i][n-1-j]

[!warning] ⚠️ Go 实现中的常见坑

1. 善用 Go 的多重赋值做 swap——a, b = b, a 简洁且安全，不需要显式声明 temp 变量。
2. 不要写两层独立的 0..n-1 转置循环——那样会把已经交换过的元素再换回来，等于没做。必须限制 j > i（只遍历上三角或下三角）。
3. 边界情况 n=1——两层循环都不会进入，直接返回原矩阵，符合预期（1×1 矩阵旋转不变）。

---

技巧

[!tip] 🔑 核心模式：镜像-旋转对偶性（Mirror-Rotation Duality）

在二维矩阵的原地变换中，多次镜像反射可以组合成任意旋转/翻转。这是因为正交群 O(2) 中的任意旋转可以由至多两次反射生成。这一性质让复杂的空间变换被拆成了简单、可验证的基础操作。

[!note] 🐹 Go 语言中的注意事项

• Go 的切片交换 a, b = b, a 是原子性的——右侧全部求值后才左侧赋值，不会像 C 那样产生中间状态。
• 对于固定大小的矩阵，可以直接访问 matrix[i][j]，无需 range 迭代器。
• 如果需要打印调试，可以用双重循环格式化输出，注意对齐宽度。

[!info] 📊 两种最优解对比

维度	逐层模拟法	转置+翻转法 ⭐
代码量	~15 行（坐标公式多）	~8 行（两个简单循环）
出错概率	较高（4 个方向坐标容易写错）	极低（转置和翻转都是基础操作）
理解难度	需要想象四层轮换	只需理解两次简单变换
面试表现	展示深度，但耗时	快速交付正确解，留时间讨论扩展

[!quote] 💬 思维延伸

这道题教会了我们一个重要的解题策略：把复杂的复合变换拆解为基础操作序列。类似的思想出现在：

• 图片编辑软件中的滤镜链（灰度 → 对比度 → 锐化）
• SVG/CSS 动画中的 transform 组合（rotate + scale + translate）
• 计算机图形学中的 MVP 矩阵（Model → View → Projection）

当你面对一个复杂的几何变换问题时，问自己：

能不能把它拆成两个或多个「明显正确的」简单步骤？

这种"组合子思维"（combinator design）在很多算法题中都奏效——比如反转链表可以先分成"前驱-后继指针三指针"两两交换，排序可以先分成"分组后组内排序再合并"。

---

代码

// rotateMatrix 将 n×n 矩阵顺时针旋转 90 度。
// 使用原地算法：先沿主对角线转置，再翻转每一行。
// 时间 O(n²)，空间 O(1)。
func rotate(matrix [][]int) {
	n := len(matrix)

	// ═══ Step 1: 沿主对角线转置（交换上三角和下三角） ═══
	// 只遍历 j > i 的区域，确保每个元素对被交换恰好一次
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}

	// ═══ Step 2: 每行左右翻转 ═══
	// 每行仅需翻转前半部分与后半部分的对应元素
	for i := 0; i < n; i++ {
		for j := 0; j < n/2; j++ {
			matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
		}
	}
}

[!success] ✅ 运行验证

这是 LeetCode 第 48 题，通过率约 75%，是一道经典的 矩阵原地变换 面试题。

• 运行时间：约 0~3 ms（Go，击败 ~99%+ 提交）
• 空间消耗：O(1) 额外空间
• 面试表现：极高。这道题的代码极其简洁，面试官通常会在正确性确认后立即追问扩展：
  • 如何逆时针旋转 90°？（转置 + 上下翻转）
  • 如何旋转 180°？（两次左右翻转 / 两次上下翻转）
  • 如果是 m×n 的非方阵怎么办？（无法原地旋转，需要额外空间）
  • 如果要求不修改矩阵呢？（用坐标映射公式计算原始索引）

[!quote] 💬 延伸思考

当你觉得某个操作很复杂时，很可能只是还没找到合适的坐标系。

旋转 90° 的本质是坐标映射 (i, j) → (j, n-1-i)。但这个公式直接实现的代价高——它需要知道哪些位置"已经被新值污染"了。而如果我们换个视角，发现转置+翻转在数学上等价于这个映射，那么代码就从"追踪每个元素的去向"简化成了"两个独立的线性扫描"。

记住这句口诀："一转二翻" —— 先转置、再翻转。下次遇到旋转矩阵的题目，条件反射即可写出最优解。