💡 一、 缘起：对官方 O(MN) 内存占用的“叛逆”

今天在刷 LeetCode 1260（二维网格迁移）时，官方给出的标准答案写得极其干净：

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> ret(m, vector<int>(n)); // 👈 扎眼的额外 M*N 空间
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int index1 = (i * n + j + k) % (m * n);
                ret[index1 / n][index1 % n] = grid[i][j];
            }
        }
        return ret;
    }
};

官方虽然巧妙地利用一维线性映射顺畅地完成了搬运，逻辑挑不出毛病，但我越看那个 ret(m, vector(n)) 越觉得心里堵得慌。

一道简单题，核心就是挪动格子，凭什么要浪费一整个矩阵的备份空间？

我的极客强迫症瞬间被点燃了。为了打破官方的 O(M * N) 辅助空间限制，我和 AI 顺着“空间备份流 -> 原地洗牌流 -> 数论降维”的线索，硬生生把这道题撕裂出了 6 种完全不同的硬核演进形态！

---

二、 拓荒阶段：那些不得不开备份数组的尝试

在最开始，我的脑子还没有跳出“必须有一个备份数组来落脚”的思维惯性，在这个阶段，我经历了三次尝试。

1. 解法一：K 次单步大循环（最暴力的模拟）

• 核心思想：开一个临时变量，每次把整个矩阵所有元素整体向右挪动 1 位，外面套一个 while(k–) 的大循环。
• 代价：空间看似省了，但由于每次移动都要扫描全场，时间复杂度高达 O(K * M * N)。只要 K 一大，LeetCode 直接用 TLE（超时）教做人。

2. 解法二：纯二维分块拼接（顺着直觉的翻车现场）

既然挪 1 位会超时，那我先克隆一份原矩阵 auto back = grid;，然后拿着算好的 newRow 和 newColmn 偏移量，试图在二维层面上把 back 矩阵的前半段和后半段对调拼接。

然而，代码一提交，无情地弹出了 Runtime Error（下标越界崩溃）。我和 AI 一对齐，发现了两个二维死穴：

• “贪吃蛇”引发的阶梯形断裂：行末尾溢出会钻到下一行开头，导致数据断开的分界线根本不是直线，而是一个“L型阶梯折线”！我的双层循环按矩形去切，漏掉了大批格子。
• 列溢出的行波及效应：在二维坐标里单纯做 i + newRow 的加减，下标会随着循环不断膨胀，直接强行撞破了内存边界。

3. 解法三：一维扁平化映射（官方的标准答案）

也就是本文开头的官方解法。在同样开辟 O(M * N) 空间的前提下，官方放弃了死磕二维分块，直接利用 i * n + j 将矩阵拍平成一维，算好新的一维索引后，再 index1 / n 填回新矩阵。没有复杂的进位判断，极其优雅，但空间代价是扎扎实实的 O(M * N)。

---

三、 突破鸿沟：多米诺环状置换，肉身洗牌

看着解法二和解法三都死死绑在“必须开辟一个额外矩阵”的耻辱柱上，我向 AI 抛出了一个更疯狂的构想：

“有没有可能彻底放弃任何备份矩阵，直接在原矩阵的‘肉身’里进行多米诺骨牌式的链式追踪（A -> B -> C -> D），强行达成时间 O(MN) + 空间真 · O(1)？”

这一句话，直接推开了离散数学中“置换群循环分解（Cyclic Decomposition）”的大门！

网格平移在物理内存上，其实可以拆解为若干个互不相交的“闭合环”（Cycles）：位置 0 的数去往 K，被挤出来的数拿过接力棒去往 (K + K) % TOTAL，直到某个数字被挤回起点 0，宣告一轮闭环。

为了让这套多米诺追踪完美落地，我们卸掉了图遍历中常见的 visited 数组（因为我们有全场总量计数器宏观控场），演进出了两种硬核的原地解法：

4. 解法四：纯 DFS 原地环状递归版（无全局污染、优雅栈流转）

利用函数的系统栈帧（局部变量 next_old_val）天生驻留在栈中的特性，让被挤出来的数字拿着接力棒自顶向下流动。由 dfs 函数在成功归位一个格子时返回 1，外层循环直接累加返回值。

class Solution {
private:
    int dfs(vector<vector<int>>& grid, int curr_1d, int start_1d, int prev_val, int k, int total, int n) {
        int next_1d = (curr_1d + k) % total;
        int next_r = next_1d / n; int next_c = next_1d % n;

        int next_old_val = grid[next_r][next_c];
        grid[next_r][next_c] = prev_val; // 原地狸猫换太子

        if (next_1d == start_1d) return 1; // 终止条件：当前环闭合

        return 1 + dfs(grid, next_1d, start_1d, next_old_val, k, total, n);
    }

public:
    vector<vector<int>>& shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(); int n = grid[0].size(); int total = m * n;
        k %= total; if (k == 0) return grid;

        int total_moved = 0; // 纯局部进度控场
        for (int start = 0; total_moved < total; ++start) {
            total_moved += dfs(grid, start, start, grid[start / n][start % n], k, total, n);
        }
        return grid;
    }
};

5. 解法五：无栈纯迭代版（真 · O(1) 空间的终极迭代形态）

递归版精美绝伦，但如果矩阵极大且形成超大单环，有系统栈溢出（Stack Overflow）的工程隐患。

我再度进行架构演进：既然手握全局计数器 count，迭代版本根本不需要任何显式或隐式的栈！直接用一个 do-while 循环让一维指针在原网格肉身内自行流转。没有任何多余空间开销，没有任何开辟大块内存的风险。

class Solution {
public:
    vector<vector<int>>& shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(); int n = grid[0].size(); int total = m * n;
        k %= total; if (k == 0) return grid;

        int count = 0; // 核心总量计数器
        for (int start = 0; count < total; ++start) {
            int curr_1d = start;
            int prev_val = grid[start / n][start % n]; // 抓起首个接力棒

            do {
                int next_1d = (curr_1d + k) % total;
                int next_r = next_1d / n; int next_c = next_1d % n;

                int temp = grid[next_r][next_c];
                grid[next_r][next_c] = prev_val; // 原地换血
                prev_val = temp;

                curr_1d = next_1d;
                count++; 
            } while (curr_1d != start); // 当前链条闭合
        }
        return grid;
    }
};

四、 艺术美学：AI 砸过来的王炸

6. 解法六：惊艳全场的三次翻转法（Vector Reverse）

就在我觉得原地环状迭代已经把这道题的空间 and 逻辑压榨到极限的时候，AI 突然在对话框里抛出了一套绝妙的代码艺术美学——矩阵版的“旋转数组”。

网格向右平移 K 位，本质上就是把逻辑一维管子里最末尾的 K 个元素整体拔起来，空降到了最车头。

我们甚至不需要写任何复杂的环路迭代，直接通过自定义 Lambda 表达式将一维索引映射为二维引用，配合 C++ 标准库的 std::swap，三行翻转，降维打击：

class Solution {
public:
    vector<vector<int>>& shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size(); int n = grid[0].size(); int total = m * n;
        k %= total; if (k == 0) return grid;

        // 一维索引到二维引用的神奇映射
        auto get_ref = [&](int idx) -> int& { return grid[idx / n][idx % n]; };
        
        auto reverse_range = [&](int start, int end) {
            while (start < end) { swap(get_ref(start), get_ref(end)); start++; end--; }
        };

        // 🏆 震撼全场的三步翻转神迹
        reverse_range(0, total - 1);     // 1. 全局大翻转（车头车尾大颠倒）
        reverse_range(0, k - 1);         // 2. 翻转前 k 个元素（局部复位）
        reverse_range(k, total - 1);     // 3. 翻转剩下的元素（局部复位）

        return grid;
    }
};

五、 王者升华：破译置换群的数论终极定理

在死磕的最后，我们将问题推向了纯数学的无上圣殿。

不管是写解法四的 DFS 还是解法五的纯迭代，我们外层循环都在兢兢业业地做 start++，并依赖计数器去盲目探索“下一个独立环的起点在哪里”。

但其实，这个矩阵里究竟存在多少个独立封闭的连通环，在数论里是一个早就被写死的定理！

📐 物理置换群循环分解定理：
在一个长度为 TOTAL 的环形链表中，每次步长为 K 进行跳跃。全场互不相交的、独立封闭的连通环个数，有且仅有：
环的个数 = gcd(TOTAL, K) = gcd(m * n, k)

💥 数学发现带来的代码进化

这意味着，我们根本连全局计数器都可以退居二线！
我们明确地知道，全场就只有 gcd(total, k) 个环。外层循环的起点，精确地锁死在 0 到 gcd(total, k) - 1 之间，一步都不会多走，逻辑坚固得像一块花岗岩！

---

六、 结语：把简单题挖到尽头的魅力

回看整场死磕，这 6 种解法完美诠释了算法探索的无上乐趣：

• 从最初粗糙的 K次单步模拟 到直觉的 二维分块翻车；
• 看到官方完美的 一维映射新矩阵解法；
• 被激发出空间强迫症，跨越空间鸿沟推导出了 真 · O(1) 空间的环状多米诺置换（DFS与纯迭代）；
• 惊叹于 AI 抛出的 三次翻转美学；
• 最终，用 最大公约数（GCD）定理 在数论层面实现终极闭环。

刷题的乐趣从来不在于 AC 数量的堆砌，而在于你能不能在一个看似简单的官方及格方案后面，把问题的底层物理结构和数学本质，挖到它无法再优化的最尽头！