LeetCode 1861. 旋转盒子【详细题解｜双指针+模拟两种解法】

LeetCode 1861. 旋转盒子【详细题解｜双指针+模拟两种解法】

一、题目概述

1.1 题目描述

给定一个m x n的字符矩阵boxGrid表示箱子侧视图，矩阵包含三种字符：

• \#：石头，受重力影响下落

• \*：固定障碍物，位置永远不变

• \.：空位置

需要完成两个核心操作：

1. 箱子顺时针旋转90度，矩阵尺寸由m\*n变为n\*m；

2. 旋转后石头受重力垂直下落，直至碰到箱子底部、障碍物或其他石头；

题目保证初始状态合法：所有石头初始都处于稳定位置（底部、石头上、障碍物上），无悬空石头。最终返回旋转+重力下落后的新矩阵。

1.2 示例展示

示例1

输入：boxGrid=[["#",".","#"]]输出：[["."],["#"],["#"]]

示例2

输入：boxGrid=[["#",".","*","."],["#","#","*","."]]输出：[["#","."],["#","#"],["*","*"],[".","."]]

1.3 数据范围

• 1 \<= m, n \<= 500

• 矩阵元素仅为\#、\*、\.三种字符

二、解题核心思路分析

2.1 过程拆解

本题难点在于理清旋转和重力下落的先后顺序与坐标映射关系，最优解题顺序为：

先模拟重力下落（原矩阵预处理）→ 再顺时针旋转90度得到结果矩阵

原因：重力是垂直向下的，在原矩阵中，每一行的重力下落逻辑独立、简单易处理；若先旋转再处理重力，坐标逻辑会变得复杂，极易出错。

2.2 核心规律

1. 重力规则：同一行中，障碍物会分割出独立区间，每个区间内的石头全部下沉到区间底部，空位填充到上方；

2. 旋转坐标规则：原矩阵m行n列，旋转后为n行m列。原矩阵坐标\(i,j\)对应新矩阵坐标\(j, m\-1\-i\)。

2.3 解法分类

• 解法一：暴力模拟法：逐行遍历，分割障碍物区间，统计石头数量，重构每一行，直观易懂；

• 解法二：双指针优化法：不开辟额外数组重构行，原地双指针移动石头，时间空间最优，适配大数据量。

三、解法一：暴力模拟预处理 + 矩阵旋转

3.1 算法思路

1. 逐行重力预处理：遍历原矩阵每一行，以\*为分割点，将每行拆分为多个独立区间；

2. 对每个区间，统计石头\#的数量，区间重构为：上方全为空位\.，下方全为石头\#；

3. 保留所有障碍物位置不变，拼接所有区间得到重力下落完成后的原矩阵；

4. 矩阵旋转：按照顺时针90度坐标映射规则，生成最终结果矩阵。

3.2 完整代码实现

fromtypingimportListclassSolution:defrotateTheBox(self,boxGrid:List[List[str]])->List[List[str]]:m=len(boxGrid)n=len(boxGrid[0])# 第一步：预处理，模拟每一行石头重力下落foriinrange(m):row=boxGrid[i]new_row=[]left=0whileleft<n:# 遇到障碍物，直接加入并跳过ifrow[left]=='*':new_row.append('*')left+=1continue# 找到当前无障碍物区间的左右边界right=left stone_cnt=0whileright<nandrow[right]!='*':ifrow[right]=='#':stone_cnt+=1right+=1# 重构区间：前方空位，后方石头empty_cnt=right-left-stone_cnt new_row.extend(['.']*empty_cnt)new_row.extend(['#']*stone_cnt)left=right# 更新当前行为重力下落后的行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]returnres

3.3 复杂度分析

• 时间复杂度：O\(m\*n\)，仅两次矩阵遍历，每个格子仅访问常数次；

• 空间复杂度：O\(m\*n\)，主要为结果矩阵开销，预处理行数组为临时开销。

四、解法二：双指针原地优化 + 矩阵旋转（最优解）

4.1 算法思路

暴力法需要额外数组重构每一行，双指针法可实现原地修改，节省临时数组空间，核心逻辑：

1. 逆序遍历每一行，定义落地指针 fall：记录当前石头可以下落的最底部位置；

2. 遇到空位\.：直接跳过；

3. 遇到石头\#：将当前石头移动到 fall 指针位置，fall 指针上移；

4. 遇到障碍物\*：障碍物位置不变，fall 指针更新为障碍物上一位（新的下落起点）；

5. 原地完成所有行的重力下落，再执行矩阵旋转，得到结果。

4.2 完整代码实现

fromtypingimportListclassSolution:defrotateTheBox(self,boxGrid:List[List[str]])->List[List[str]]:m=len(boxGrid)n=len(boxGrid[0])# 第一步：双指针原地处理重力下落foriinrange(m):# fall指针：当前石头可下落的最低位置，初始为行末尾fall=n-1# 逆序遍历每一列forjinrange(n-1,-1,-1):# 遇到障碍物：更新下落位置，障碍物位置保留ifboxGrid[i][j]=='*':fall=j-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]returnres

4.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\)

推导逻辑：

1. 原矩阵第i行，旋转后变为新矩阵倒数第i列；

2. 原矩阵第j列，旋转后变为新矩阵第j行；

3. 最终映射为res\[j\]\[m\-1\-i\] = boxGrid\[i\]\[j\]。

5.2 重力模拟关键细节

• 必须逆序遍历行：从行尾向行头遍历，保证石头下落时不会覆盖未遍历的石头；

• 障碍物是天然分隔边界：每个障碍物右侧是独立的下落区间，fall指针实时重置，保证区间隔离；

• 先置空再赋值：移动石头时先将原位置置空，再写入下落位置，避免数据覆盖错误。

六、代码测试验证

使用示例2数据测试双指针解法：

if__name__=="__main__":sol=Solution()box=[["#",".","*","."],["#","#","*","."]]print(sol.rotateTheBox(box))# 输出：[['#','.'],['#','#'],['*','*'],['.','.']]

七、总结

1. 解题最优顺序：先重力下落、后矩阵旋转，大幅降低逻辑复杂度；

2. 暴力法：逻辑直观、适合新手理解原理，空间开销略大；

3. 双指针法：原地修改、时空最优，是面试刷题首选解法；

4. 核心考点：矩阵旋转坐标映射+线性遍历模拟重力，是矩阵类经典题型。