当前位置：首页 > news >正文

【空间压榨到倒计时】真 · O(1) 原地起飞：我与 AI 死磕 LeetCode 1260 的 6 阶进化录

news 2026/6/12 1:27:19

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

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

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

官方虽然巧妙地利用一维线性映射顺畅地完成了搬运，逻辑挑不出毛病，但我越看那个 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，外层循环直接累加返回值。

classSolution{private:intdfs(vector<vector<int>>&grid,intcurr_1d,intstart_1d,intprev_val,intk,inttotal,intn){intnext_1d=(curr_1d+k)%total;intnext_r=next_1d/n;intnext_c=next_1d%n;intnext_old_val=grid[next_r][next_c];grid[next_r][next_c]=prev_val;// 原地狸猫换太子if(next_1d==start_1d)return1;// 终止条件：当前环闭合return1+dfs(grid,next_1d,start_1d,next_old_val,k,total,n);}public:vector<vector<int>>&shiftGrid(vector<vector<int>>&grid,intk){intm=grid.size();intn=grid[0].size();inttotal=m*n;k%=total;if(k==0)returngrid;inttotal_moved=0;// 纯局部进度控场for(intstart=0;total_moved<total;++start){total_moved+=dfs(grid,start,start,grid[start/n][start%n],k,total,n);}returngrid;}};

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

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

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

classSolution{public:vector<vector<int>>&shiftGrid(vector<vector<int>>&grid,intk){intm=grid.size();intn=grid[0].size();inttotal=m*n;k%=total;if(k==0)returngrid;intcount=0;// 核心总量计数器for(intstart=0;count<total;++start){intcurr_1d=start;intprev_val=grid[start/n][start%n];// 抓起首个接力棒do{intnext_1d=(curr_1d+k)%total;intnext_r=next_1d/n;intnext_c=next_1d%n;inttemp=grid[next_r][next_c];grid[next_r][next_c]=prev_val;// 原地换血prev_val=temp;curr_1d=next_1d;count++;}while(curr_1d!=start);// 当前链条闭合}returngrid;}};

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

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

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

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

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

classSolution{public:vector<vector<int>>&shiftGrid(vector<vector<int>>&grid,intk){intm=grid.size();intn=grid[0].size();inttotal=m*n;k%=total;if(k==0)returngrid;// 一维索引到二维引用的神奇映射autoget_ref=[&](intidx)->int&{returngrid[idx/n][idx%n];};autoreverse_range=[&](intstart,intend){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. 翻转剩下的元素（局部复位）returngrid;}};