题目描述
思路解析
一句话答案：LeetCode 1861 旋转盒子：顺时针转 90 度后向右恰好变成向下，于是先让每行石头在原图向右靠拢再整体旋转，一遍矩阵模拟即可，时间 O(m·n)、空间 O(m·n)。
旋转加重力，最后要返回什么形状
给一个 m 行 n 列的字符箱子 box，井号是石头、星号是固定障碍物、点是空位。把整个箱子顺时针转 90 度，重力立刻生效，石头垂直下落，直到压在障碍物、别的石头或箱子底部才停，障碍物钉死不动。题面例子是 2 行 4 列，转完要返回 4 行 2 列——行列尺寸从 m 行 n 列换成 n 行 m 列，这点先记牢。
真把图转过来再一格格往下砸，累在哪
先真把矩阵转出来、再让每颗石头一格格往下砸，是最贴题意的走法：扫一遍网格，石头正下方是空位就挪它下去一格，一趟到不了底就再扫，直到整张图不再变。它能算对，可一颗石头最坏落 n 格、每趟又要扫全图，掉到底可能要 O(n) 趟，合起来奔着 O(m·n·max(m,n)) 去，反复扫到稳定的退出条件也容易写错。
凭什么旋转前就敢让石头先向右靠拢
绕开反复下落，靠的是把旋转和重力拆开看。顺时针转 90 度会把方向也一起转过去：原图里的向右，转完恰好对应新图里的向下。既然如此，与其转完再让石头往下掉，不如旋转前就在原图每行里让石头向右靠拢到位，再把靠好的图整体转过去，两种顺序落点完全一样。重力就这样被提前化成每行向右滑这件一维小事，剩下的旋转只是纯粹搬格子。
每行怎么靠拢，障碍物把它切成几段
障碍物是死挡板，把一行切成几段互不相通的区间，石头只能在自己那段里滑、穿不过障碍物到隔壁段。于是从这行最右端往左扫，把遇到的空位记成落脚点：扫到障碍物，攒的落脚点全部清空，因为它右边的空位帮不了左边的石头；扫到石头，右侧同段还留着落脚点就滑过去占最靠右那个、腾出的空位再补回，同段没有则不动。参考代码用一个队列 deque 存空位下标、从队头取最靠右的；换个写指针从右往左原地摆放也一样。
题面那个 2 行 4 列箱子，两步各走出什么
拿题面的 box=[["#",".","*","."],["#","#","*","."]] 走两步。先靠拢：行 0 = ["#",".","*","."]，障碍物在第 2 列，把这行切成第 0-1 列与第 3 列两段；左段第 0 列的石头向右滑一格到第 1 列，行 0 成 [".","#","*","."]。行 1 = ["#","#","*","."] 的两颗石头本就贴着障碍物、无处可滑，整行不动。
再旋转：顺时针转 90 度，底行行 1 竖成结果最左列，顶行行 0 竖成最右列。左列自上而下是石头、石头、障碍物、空位；右列是空位、石头、障碍物、空位。两列并起来就是 [["#","."],["#","#"],["*","*"],[".","."]]，和题面答案一致。
O(m·n) 之外，单行和空行别漏想
每个格子在旋转拷贝时搬一次、靠拢时入队出队常数次，时间 O(m·n)，至少得读遍所有格子，已是下界；答案矩阵占 O(m·n)，另加存空位下标的队列 O(max(m,n))。只有一行也不特殊，靠拢在这行内做完再竖过来；整行没石头就只旋转、不移动；石头贴着右墙或障碍物、同段无落脚点就留在原地。真正坑人的是结果尺寸：转完是 n 行 m 列而非 m 行 n 列，新数组得按行列互换后的形状开，沿用原尺寸会越界。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这两步:先让每行石头向右靠拢、遇障碍物断开,再把整张图顺时针旋转。下面每一帧都在套这两步,先从第一行的靠拢开始。
阶段一 · 每行向右靠拢：这就是 2 行 4 列的箱子,井号是石头,星号是障碍物,点是空位。咱们先一行一行让石头向右靠拢。右边面板记这一行右侧有哪些空位能落脚,现在从行 0 开始,从最右边往左扫。
行 0 · 第 3 列是空位：行 0 扫到第 3 列,是空位。把它记进右边面板,当作后面石头可以滑过来的落脚点。现在这一行右侧能落脚的空位有 1 个。
行 0 · 第 2 列是障碍物：行 0 扫到第 2 列,是障碍物星号。石头穿不过障碍物,所以障碍物右边攒下的落脚点在这里全部作废,面板清空。障碍物左边的石头只能落在障碍物这一侧,和右边互不相通。
行 0 · 第 1 列是空位：行 0 扫到第 1 列,是空位。把它记进右边面板,当作后面石头可以滑过来的落脚点。现在这一行右侧能落脚的空位有 1 个。
行 0 · 第 0 列石头要向右滑：行 0 扫到第 0 列,是一颗石头。它右边最近的空位在第 1 列。重力让它向右滑,它要从第 0 列滚到第 1 列去。
行 0 · 石头落在第 1 列：石头落在第 1 列,原来的第 0 列空了出来。这个新腾出的空位接着记进面板,留给它左边可能还有的石头用。
行 0 靠拢完成：行 0 靠拢完成,石头都贴到了障碍物左边。原来它散在第 0 列,现在滑到了第 1 列,紧挨着障碍物。接着处理行 1。
行 1 · 第 3 列是空位：行 1 扫到第 3 列,是空位。把它记进右边面板,当作后面石头可以滑过来的落脚点。现在这一行右侧能落脚的空位有 1 个。
行 1 · 第 2 列是障碍物：行 1 扫到第 2 列,是障碍物星号。石头穿不过障碍物,所以障碍物右边攒下的落脚点在这里全部作废,面板清空。障碍物左边的石头只能落在障碍物这一侧,和右边互不相通。
行 1 · 第 1 列石头不动：行 1 扫到第 1 列,是一颗石头,它右边马上就是障碍物,同一段里没有可落脚的空位,所以它已经靠到位,原地不动。
行 1 · 第 0 列石头不动：行 1 扫到第 0 列,是一颗石头,它右边同一段内已被第 1 列石头占住,再往右被障碍物截断,没有可用的落脚点,它已经靠到位,原地不动。
行 1 靠拢完成：行 1 靠拢完成。这一行的两颗石头本来就贴着障碍物,障碍物左侧这一段没有空位;第 3 列虽然是空位,却被障碍物隔开,给不了左侧的石头用,所以两颗石头原地没动。两行都靠拢好了。
阶段一完成 · 每行都靠拢好：两行的石头都向右靠拢好了。为什么可以在旋转前就这么做?因为顺时针转 90 度之后,原来的向右恰好变成向下,旋转后石头往下掉,等价于旋转前让它们先向右滑到位。现在只剩纯粹的旋转这一步了。
阶段二 · 准备顺时针旋转：开始旋转。顺时针转 90 度有个好记的规律:原来的底行,会变成结果的左列;原来的顶行,会变成结果的右列。这里先把底行,也就是行 1 的这四个格子高亮出来,它们待会儿会竖着排到结果的最左边一列。
底行第 0 列 → 结果左列第 0 行：底行从左往右第 0 个是石头(井号),顺时针转过去,它落到结果左列从上往下第 0 行。继续放下一个。
底行第 1 列 → 结果左列第 1 行：底行从左往右第 1 个是石头(井号),顺时针转过去,它落到结果左列从上往下第 1 行。继续放下一个。
底行第 2 列 → 结果左列第 2 行：底行从左往右第 2 个是障碍物(星号),顺时针转过去,它落到结果左列从上往下第 2 行。继续放下一个。
底行第 3 列 → 结果左列第 3 行：底行从左往右第 3 个是空位(点),顺时针转过去,它落到结果左列从上往下第 3 行。结果的左列这就填满了。
结果左列填好：结果的左列填好了,从上到下是石头、石头、障碍、空,正是原来底行从左到右的顺序竖过来。接着把顶行,也就是行 0,放到结果的右列。
顶行第 0 列 → 结果右列第 0 行：顶行从左往右第 0 个是空位(点),顺时针转过去,它落到结果右列从上往下第 0 行。继续放下一个。
顶行第 1 列 → 结果右列第 1 行：顶行从左往右第 1 个是石头(井号),顺时针转过去,它落到结果右列从上往下第 1 行。继续放下一个。
顶行第 2 列 → 结果右列第 2 行：顶行从左往右第 2 个是障碍物(星号),顺时针转过去,它落到结果右列从上往下第 2 行。继续放下一个。
顶行第 3 列 → 结果右列第 3 行：顶行从左往右第 3 个是空位(点),顺时针转过去,它落到结果右列从上往下第 3 行。结果的右列也填满了。
旋转完成 · 4 行 2 列结果：整张图转完了,结果是 4 行 2 列。回看全程,咱们没有真的去转图,而是先让每行石头向右靠拢模拟掉落,再按顺时针把底行变左列、顶行变右列排好。这个结果和题目样例 2 给的答案一模一样。
边界想清:单行时靠拢在这一行内完成再竖过来、整行无石头就只旋转不移动、石头已贴右墙就原地不动。
面试重点:旋转把向右带成向下所以先靠拢再转等价、靠拢那步可用双指针原地做省掉队列、O(m 乘 n) 已是下界无法更低。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def rotateTheBox(self, boxGrid: List[List[str]]) -> List[List[str]]: m, n = len(boxGrid), len(boxGrid[0]) ans = [[None] * m for _ in range(n)] for i in range(m): for j in range(n): ans[j][m - i - 1] = boxGrid[i][j] for j in range(m): q = deque() for i in range(n - 1, -1, -1): if ans[i][j] == "*": q.clear() elif ans[i][j] == ".": q.append(i) elif q: ans[q.popleft()][j] = "#" ans[i][j] = "." q.append(i) return ans复杂度
- 时间：O(m·n)，m 是原矩阵行数,n 是列数。旋转拷贝把每个格子搬一次是 O(m·n);之后逐列从下往上扫,每个格子只入队或出队常数次,也是 O(m·n)。合起来仍是 O(m·n),必须至少读一遍所有格子,这已是下界
- 空间：O(m·n)，要新建并返回一个 n 行 m 列的答案矩阵,这是题目要求的输出,占 O(m·n)。除答案之外只多用一个队列存空位下标,额外空间是 O(max(m,n));若不计必须返回的答案矩阵,额外空间就是 O(max(m,n))
易错点
面试追问把动画讲成自己的话
追问为什么可以先靠拢再旋转,和先旋转再让石头下落结果一样?
追问每行靠拢那一步,能不能不用队列,用两个指针原地做?
追问这题时间复杂度还能不能更低?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
向字符串添加空格
LeetCode 2109 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题