算法笔记：矩阵分层旋转问题 —— 从「层」到「四指针」的思维转换

日期: 2026-05-09
难度: Medium
标签: 矩阵、模拟、循环旋转

题目描述

给定一个 m × n 的二维网格 grid 和一个整数 k。你需要将 grid 按逆时针方向循环旋转每一层，旋转 k 次。

所谓「一层」就是从外到内的一圈元素。旋转时，各层独立旋转。

第一次思路（卡住了）

刚开始我的思路是这样的：

遍历层数为 level = min(m, n) / 2
最开始高宽为 m 和 n，每缩一层长宽减 2
当处在某一层的高宽为 h 和 w 时，一圈的元素个数为 2 * (w + h - 2)

想法是对的，但问题在于无法用一个「层序号」去直接映射到二维数组的下标。比如我知道我在第 3 层，那这一圈的左上角坐标是多少？不知道。代码写着写着就变成了各种 +1 -1 的边界调整，非常容易出 bug。

最终方案：四个方向变量

这个问题的核心痛点在于如何方便地遍历和修改某一圈的元素。与其算「第几层」，不如直接维护四个指针：

top    — 当前层的上边界行号
bottom — 当前层的下边界行号
left   — 当前层的左边界列号
right  — 当前层的右边界列号

每处理完一层，top++, left++ 往里缩一圈，bottom--, right-- 同理。

这样不但代码可读性好，而且完全避免了「层号 ⇔ 数组下标」的尴尬映射。

提取 + 旋转 + 填回

提取（逆时针顺序）：

从 top 行开始，沿 left 列向下走到底         → grid[top..bottom][left]
从 bottom 行开始，沿 left+1 列向右走到右边界  → grid[bottom][left+1..right]
从 bottom-1 行开始，沿 right 列向上走到最上面  → grid[bottom-1..top][right]
从 right-1 列开始，沿 top 行向左走到 left+1    → grid[top][right-1..left+1]

⚠️ 注意：四个方向的遍历要注意重叠端点不能重复取。

旋转：

由于 k 可以非常大，不能老老实实转 k 次。一圈的元素个数 len = 2 * (w + h - 2)，只需要 k %= len 然后对一维数组做一次循环右移即可。

循环右移可以用三次反转来实现（原地 O(1) 空间）：

reverse(nums)
reverse(nums, nums + k)
reverse(nums + k, nums + len)

填回：

按照提取时完全相同的顺序，从旋转后的数组依次取数填回去即可。

完整代码

class Solution {
public:
    void rotateK(vector<int>& nums, int k) {
        int len = nums.size();
        if (len <= 1) return;
        k %= len;
        if (k == 0) return;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }

    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        while (top < bottom && left < right) {
            vector<int> nums;
            // 逆时针提取一圈
            for (int r = top; r <= bottom; r++) nums.push_back(grid[r][left]);
            for (int c = left + 1; c <= right; c++) nums.push_back(grid[bottom][c]);
            for (int r = bottom - 1; r >= top; r--) nums.push_back(grid[r][right]);
            for (int c = right - 1; c > left; c--) nums.push_back(grid[top][c]);

            rotateK(nums, k);  // 循环左移

            // 按相同顺序填回
            int idx = 0;
            for (int r = top; r <= bottom; r++) grid[r][left] = nums[idx++];
            for (int c = left + 1; c <= right; c++) grid[bottom][c] = nums[idx++];
            for (int r = bottom - 1; r >= top; r--) grid[r][right] = nums[idx++];
            for (int c = right - 1; c > left; c--) grid[top][c] = nums[idx++];

            top++, left++, bottom--, right--;
        }
        return grid;
    }
};

复杂度分析

复杂度	分析
时间复杂度	O(m × n) — 每个元素被访问常数次（提取一次、填回一次）
空间复杂度	O(min(m, n)) — 临时存储一圈元素的数组，最大长度为 2 × (m + n - 2)

心得总结

这道题最有价值的不是算法本身，而是它暴露了一个常见的思维陷阱：

一维思维处理二维问题时，不要硬用「层号」去映射坐标，直接用「指针」去框定范围。

我一开始用 level 变量，想着每层都是矩形，套公式算偏移量就行了。结果代码越写越乱，边界全是魔法数字。换成 top/bottom/left/right 四个指针后，思路一下就清晰了，提取和填回的逻辑完全对称，不容易出错。

这也让我想起了另一个经验：用「范围」而不是「序号」来描述二维区域。序号是间接的，每次都要换算；范围是直接的，看一眼就知道在操作哪一块。

算法笔记：矩阵分层旋转——从「层」到「四指针」的思维转换