LeetCode 1861. 旋转盒子【详细题解双指针模拟两种解法】一、题目概述1.1 题目描述给定一个m x n的字符矩阵boxGrid表示箱子侧视图矩阵包含三种字符\#石头受重力影响下落\*固定障碍物位置永远不变\.空位置需要完成两个核心操作箱子顺时针旋转90度矩阵尺寸由m\*n变为n\*m旋转后石头受重力垂直下落直至碰到箱子底部、障碍物或其他石头题目保证初始状态合法所有石头初始都处于稳定位置底部、石头上、障碍物上无悬空石头。最终返回旋转重力下落后的新矩阵。1.2 示例展示示例1输入boxGrid[[#,.,#]]输出[[.],[#],[#]]示例2输入boxGrid[[#,.,*,.],[#,#,*,.]]输出[[#,.],[#,#],[*,*],[.,.]]1.3 数据范围1 \lt; m, n \lt; 500矩阵元素仅为\#、\*、\.三种字符二、解题核心思路分析2.1 过程拆解本题难点在于理清旋转和重力下落的先后顺序与坐标映射关系最优解题顺序为先模拟重力下落原矩阵预处理→ 再顺时针旋转90度得到结果矩阵原因重力是垂直向下的在原矩阵中每一行的重力下落逻辑独立、简单易处理若先旋转再处理重力坐标逻辑会变得复杂极易出错。2.2 核心规律重力规则同一行中障碍物会分割出独立区间每个区间内的石头全部下沉到区间底部空位填充到上方旋转坐标规则原矩阵m行n列旋转后为n行m列。原矩阵坐标\(i,j\)对应新矩阵坐标\(j, m\-1\-i\)。2.3 解法分类解法一暴力模拟法逐行遍历分割障碍物区间统计石头数量重构每一行直观易懂解法二双指针优化法不开辟额外数组重构行原地双指针移动石头时间空间最优适配大数据量。三、解法一暴力模拟预处理 矩阵旋转3.1 算法思路逐行重力预处理遍历原矩阵每一行以\*为分割点将每行拆分为多个独立区间对每个区间统计石头\#的数量区间重构为上方全为空位\.下方全为石头\#保留所有障碍物位置不变拼接所有区间得到重力下落完成后的原矩阵矩阵旋转按照顺时针90度坐标映射规则生成最终结果矩阵。3.2 完整代码实现fromtypingimportListclassSolution:defrotateTheBox(self,boxGrid:List[List[str]])-List[List[str]]:mlen(boxGrid)nlen(boxGrid[0])# 第一步预处理模拟每一行石头重力下落foriinrange(m):rowboxGrid[i]new_row[]left0whileleftn:# 遇到障碍物直接加入并跳过ifrow[left]*:new_row.append(*)left1continue# 找到当前无障碍物区间的左右边界rightleft stone_cnt0whilerightnandrow[right]!*:ifrow[right]#:stone_cnt1right1# 重构区间前方空位后方石头empty_cntright-left-stone_cnt new_row.extend([.]*empty_cnt)new_row.extend([#]*stone_cnt)leftright# 更新当前行为重力下落后的行boxGrid[i]new_row# 第二步顺时针旋转90度m*n - n*mres[[None]*mfor_inrange(n)]foriinrange(m):forjinrange(n):res[j][m-1-i]boxGrid[i][j]returnres3.3 复杂度分析时间复杂度O\(m\*n\)仅两次矩阵遍历每个格子仅访问常数次空间复杂度O\(m\*n\)主要为结果矩阵开销预处理行数组为临时开销。四、解法二双指针原地优化 矩阵旋转最优解4.1 算法思路暴力法需要额外数组重构每一行双指针法可实现原地修改节省临时数组空间核心逻辑逆序遍历每一行定义落地指针 fall记录当前石头可以下落的最底部位置遇到空位\.直接跳过遇到石头\#将当前石头移动到 fall 指针位置fall 指针上移遇到障碍物\*障碍物位置不变fall 指针更新为障碍物上一位新的下落起点原地完成所有行的重力下落再执行矩阵旋转得到结果。4.2 完整代码实现fromtypingimportListclassSolution:defrotateTheBox(self,boxGrid:List[List[str]])-List[List[str]]:mlen(boxGrid)nlen(boxGrid[0])# 第一步双指针原地处理重力下落foriinrange(m):# fall指针当前石头可下落的最低位置初始为行末尾falln-1# 逆序遍历每一列forjinrange(n-1,-1,-1):# 遇到障碍物更新下落位置障碍物位置保留ifboxGrid[i][j]*:fallj-1# 遇到石头移动到fall位置fall上移elifboxGrid[i][j]#:boxGrid[i][j].boxGrid[i][fall]#fall-1# 第二步顺时针旋转90度res[[None]*mfor_inrange(n)]foriinrange(m):forjinrange(n):res[j][m-1-i]boxGrid[i][j]returnres4.3 算法优势空间更优无临时行数组仅使用常数额外变量空间复杂度优化为O\(1\)不计结果输出数组效率更高单次遍历完成重力模拟代码极简常数级开销更小适配大数据完美适配题目 500*500 最大数据量无超时风险。4.4 复杂度分析时间复杂度O\(m\*n\)两次线性遍历矩阵空间复杂度O\(1\)额外空间结果数组为题目必须输出不计入算法空间开销。五、核心难点详解5.1 旋转坐标映射推导原矩阵m行n列旋转后n行m列顺时针旋转90度通用坐标公式原坐标\(i, j\)→ 新坐标\(j, m\-1\-i\)推导逻辑原矩阵第i行旋转后变为新矩阵倒数第i列原矩阵第j列旋转后变为新矩阵第j行最终映射为res\[j\]\[m\-1\-i\] boxGrid\[i\]\[j\]。5.2 重力模拟关键细节必须逆序遍历行从行尾向行头遍历保证石头下落时不会覆盖未遍历的石头障碍物是天然分隔边界每个障碍物右侧是独立的下落区间fall指针实时重置保证区间隔离先置空再赋值移动石头时先将原位置置空再写入下落位置避免数据覆盖错误。六、代码测试验证使用示例2数据测试双指针解法if__name____main__:solSolution()box[[#,.,*,.],[#,#,*,.]]print(sol.rotateTheBox(box))# 输出[[#,.],[#,#],[*,*],[.,.]]七、总结解题最优顺序先重力下落、后矩阵旋转大幅降低逻辑复杂度暴力法逻辑直观、适合新手理解原理空间开销略大双指针法原地修改、时空最优是面试刷题首选解法核心考点矩阵旋转坐标映射线性遍历模拟重力是矩阵类经典题型。