题目描述
思路解析动画文字版
记牢这两步:先让每行石头向右靠拢、遇障碍物断开,再把整张图顺时针旋转。下面每一帧都在套这两步,先从第一行的靠拢开始。
阶段一 · 每行向右靠拢：这就是 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题