LeetCode 1861. Rotating the Box 全解：重力模拟 + 二维矩阵旋转的组合题实战（NeetCode 仓库解析）

LeetCode 1861. Rotating the Box 全解重力模拟 二维矩阵旋转的组合题实战NeetCode 仓库解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于本仓库 articles/rotating-the-box.md 展开系统讲解 LeetCode 1861 Rotating the Box 的完整解题思路。该题把「重力模拟」与「90 度顺时针旋转」两个高频技巧揉进一道题里是面试中考察二维数组操作基本功的典型题目。读完本文你将掌握三种层层递进的解法——从 O(m·n²) 的暴力模拟到 O(m·n) 的双指针优化再到「重力 旋转一步到位」的单趟写法并能在 Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust 九种语言中直接套用。问题背景与核心模型给定一个m x n的二维字符网格boxGrid每个格子是以下三种字符之一字符含义旋转后行为#石头stone受重力影响向新方向下落*固定障碍物obstacle位置固定挡住石头.空位empty可供石头落入要求先将整个箱子顺时针旋转 90 度再让所有石头在新方向上受重力下落即向新箱子的底部沉最后返回旋转并完成重力沉降后的网格。关键观察先想清旋转后重力朝哪旋转前网格有ROWS行、COLS列旋转 90 度顺时针后新网格有COLS行、ROWS列且原位置(r, c)上的元素会映射到新位置(c, ROWS - 1 - r)——这与仓库中另一篇矩阵旋转题解 rotate-matrix.md 使用的坐标变换公式(i, j) - (j, n - 1 - i)完全一致。旋转后重力朝下等价于旋转前石头在每一行内向右侧列索引增大的方向沉降。因此可以分两步思考先模拟行内重力让每行的#尽量向右移动直到被*或右边界挡住再做坐标旋转把处理后的网格按顺时针 90 度映射到新网格。这一旋转前先横向落石的思路是把复杂的二维问题降解为若干个独立一维问题的关键。前置知识Prerequisites二维数组操作熟悉网格的行列索引能在原地读写元素双指针技巧用一个指针记录下一个可用位置遍历时把元素移动到目标位置可对照仓库中 move-zeroes.md 的快慢指针思想重力模拟让元素沿某一方向移动直到撞上障碍或边界矩阵旋转掌握 90 度顺时针旋转的坐标映射(r, c) - (c, ROWS - 1 - r)。解法一Brute Force暴力扫描思路最直观的做法对每一行从右向左遍历。遇到石头#时向右扫描找到最远的空位把石头搬过去。因为从右向左处理先处理右边的石头不会影响左边石头的判断而每块石头只向右移动右侧已经落定的石头不会阻碍扫描。处理完全部行后再把网格旋转新网格有COLS行第c行由原网格第c列从下往上读取得到。算法步骤对每一行r从右往左遍历每一列c1若boxGrid[r][c1] #令c2 c1 1向右扫描所有连续的空位.遇到*或越界即停把石头移动到c2 - 1最右可达空位原位置置为.全部行处理完后构造结果网格resres有COLS行、ROWS列res[c]的元素来自原网格第c列自底向上返回res。参考实现Pythonclass Solution: def rotateTheBox(self, boxGrid: List[List[str]]) - List[List[str]]: ROWS, COLS len(boxGrid), len(boxGrid[0]) for r in range(ROWS - 1, -1, -1): for c1 in range(COLS - 1, -1, -1): if boxGrid[r][c1] #: c2 c1 1 while c2 COLS and boxGrid[r][c2] .: c2 1 boxGrid[r][c1] . boxGrid[r][c2 - 1] # res [] for c in range(COLS): col [] for r in range(ROWS - 1, -1, -1): col.append(boxGrid[r][c]) res.append(col) return resCclass Solution { public: vectorvectorchar rotateTheBox(vectorvectorchar boxGrid) { int ROWS boxGrid.size(), COLS boxGrid[0].size(); for (int r ROWS - 1; r 0; r--) { for (int c1 COLS - 1; c1 0; c1--) { if (boxGrid[r][c1] #) { int c2 c1 1; while (c2 COLS boxGrid[r][c2] .) { c2; } boxGrid[r][c1] .; boxGrid[r][c2 - 1] #; } } } vectorvectorchar res(COLS, vectorchar(ROWS)); for (int c 0; c COLS; c) { for (int r ROWS - 1; r 0; r--) { res[c][ROWS - 1 - r] boxGrid[r][c]; } } return res; } };Java、JavaScript、C#、Go、Kotlin、Swift、Rust 的实现逻辑完全一致详见 articles/rotating-the-box.md 的多语言标签页。以 Java 为例旋转映射写作res[c][ROWS - 1 - r] boxGrid[r][c]即从原网格第c列自底向上填充结果第c行Go 与 Rust 版本同理仅需注意 Rust 中c2 - 1的写法需保证不越界。复杂度分析时间复杂度$O(m \cdot n^2)$ —— 最坏情况下每块石头都可能向右扫描很长一段空位空间复杂度$O(m \cdot n)$ —— 结果网格占用额外空间。其中 $m$ 为行数$n$ 为列数。解法二Two Pointers - I双指针优化落石思路暴力解对每块石头都重新扫描空位存在大量重复工作。改用双指针维护指针i表示当前行中最右侧的可落石位置。从右向左扫描遇到石头#与位置i交换然后i--遇到障碍*把i重置为c - 1障碍左侧第一个位置。这样每个格子至多被访问两次无需为每块石头单独扫描时间复杂度降为 $O(m \cdot n)$。算法步骤对每行初始化i COLS - 1最右侧位置从右向左遍历该行若为#与boxGrid[r][i]交换i--若为*i c - 1所有行处理完后按每列自底向上构造旋转结果返回结果。参考实现Pythonclass Solution: def rotateTheBox(self, boxGrid: List[List[str]]) - List[List[str]]: ROWS, COLS len(boxGrid), len(boxGrid[0]) for r in range(ROWS): i COLS - 1 for c in reversed(range(COLS)): if boxGrid[r][c] #: boxGrid[r][c], boxGrid[r][i] boxGrid[r][i], boxGrid[r][c] i - 1 elif boxGrid[r][c] *: i c - 1 res [] for c in range(COLS): col [] # 旋转后这一列变成一行 for r in reversed(range(ROWS)): col.append(boxGrid[r][c]) res.append(col) return resGofunc rotateTheBox(boxGrid [][]byte) [][]byte { ROWS, COLS : len(boxGrid), len(boxGrid[0]) for r : 0; r ROWS; r { i : COLS - 1 for c : COLS - 1; c 0; c-- { if boxGrid[r][c] # { boxGrid[r][c], boxGrid[r][i] boxGrid[r][i], boxGrid[r][c] i-- } else if boxGrid[r][c] * { i c - 1 } } } res : make([][]byte, COLS) for c : 0; c COLS; c { res[c] make([]byte, ROWS) for r : ROWS - 1; r 0; r-- { res[c][ROWS-1-r] boxGrid[r][c] } } return res }其余语言Java / C / JavaScript / C# / Kotlin / Swift / Rust的完整实现见 articles/rotating-the-box.md。注意 Rust 版本为了处理i可能减到 0 以下的情况使用了wrapping_sub(1)规避下溢。复杂度分析时间复杂度$O(m \cdot n)$ —— 每行一次从右到左扫描每格常数次操作空间复杂度$O(m \cdot n)$ —— 结果网格占用的额外空间。解法三Two Pointers - II重力 旋转合并为单趟思路前两种解法都是先落石、后旋转两步走且都会修改原网格。解法三更进一步直接把每个元素写到它在旋转后网格中的最终位置在单趟遍历里同时完成重力模拟与旋转不修改输入网格。做法先建一个COLS x ROWS、全部填充.的结果网格遍历原网格每一行时仍用指针i记录本行从右往左数下一个可放石头的位置。旋转映射为障碍*写到res[c][ROWS - r - 1]并把i重置为c - 1石头#写到res[i][ROWS - r - 1]然后i--。由于重力沉降发生在旋转前的每一行内i恰好对应旋转后该行石头堆叠的新列位置一次遍历即可得到最终答案。算法步骤初始化结果网格resCOLS行 ×ROWS列全部填充.遍历原网格每一行r初始化i COLS - 1从右向左遍历列c若为#res[i][ROWS - r - 1] #i--若为*res[c][ROWS - r - 1] *i c - 1返回res。参考实现Pythonclass Solution: def rotateTheBox(self, boxGrid: List[List[str]]) - List[List[str]]: ROWS, COLS len(boxGrid), len(boxGrid[0]) res [[.] * ROWS for _ in range(COLS)] for r in range(ROWS): i COLS - 1 for c in reversed(range(COLS)): if boxGrid[r][c] #: res[i][ROWS - r - 1] # i - 1 elif boxGrid[r][c] *: res[c][ROWS - r - 1] * i c - 1 return resJavaScriptclass Solution { /** * param {character[][]} boxGrid * return {character[][]} */ rotateTheBox(boxGrid) { const ROWS boxGrid.length, COLS boxGrid[0].length; const res Array.from({ length: COLS }, () Array(ROWS).fill(.)); for (let r 0; r ROWS; r) { let i COLS - 1; for (let c COLS - 1; c 0; c--) { if (boxGrid[r][c] #) { res[i][ROWS - r - 1] #; i--; } else if (boxGrid[r][c] *) { res[c][ROWS - r - 1] *; i c - 1; } } } return res; } }C、Java、C#、Go、Kotlin、Swift、Rust 的完整实现同样收录于 articles/rotating-the-box.md。复杂度分析时间复杂度$O(m \cdot n)$空间复杂度$O(m \cdot n)$结果网格本身即是返回值若不把返回值计入额外空间则除结果外无额外空间开销。三种解法的落石部分均为原地操作区别仅在于旋转阶段的组织方式。解法三不修改输入、代码最精简是面试中推荐优先呈现的写法。三种解法对比解法策略时间空间是否修改输入解法一 Brute Force每块石头向右扫描最远空位后搬移$O(m \cdot n^2)$$O(m \cdot n)$是解法二 Two Pointers - I指针记录最右可落石位置边扫边交换$O(m \cdot n)$$O(m \cdot n)$是解法三 Two Pointers - II单趟遍历直接写入旋转后结果$O(m \cdot n)$$O(m \cdot n)$否常见陷阱Common Pitfalls陷阱一重力方向搞反旋转后重力朝下因此旋转前石头应在本行内向右列索引增大方向沉降。若从左向右处理石头先落的石头会挡住后面石头的去路导致落石错误。务必从右向左遍历每一行。陷阱二遇到障碍后忘记重置落石指针双指针写法中遇到*时必须把i重置为c - 1障碍左侧一格。若忘记重置石头会穿过障碍物或在障碍物上方错误堆叠。暴力法中对应地要保证向右扫描在遇到*时立即停止。陷阱三旋转坐标映射写错90 度顺时针旋转的映射是(r, c) - (c, ROWS - 1 - r)。若误写成(c, r)转置或(ROWS - 1 - r, c)水平翻转 转置得到的将是转置或镜像矩阵而非真正的旋转结果。检验方法用一个小例子如 2×3 网格手工推导一遍目标位置。延伸思考与仓库中同类题目的关联这道题的技巧可以拆解为两个可复用的组件在仓库中均有对应题解可以对照学习矩阵旋转坐标映射(r, c) - (c, ROWS - 1 - r)与 rotate-matrix.md 中 90 度顺时针旋转的推导一致该文还讲解了转置 逐行反转的原地旋转写法可作为本解法旋转阶段的补充读物双指针 方向性移动行内石头向右堆、指针记录落点的思想与 move-zeroes.md把非零元素向左聚拢本质上是同一类按方向筛选并重排元素的双指针模式遇到障碍分区处理的结构则与 sort-colors.md 的分区思想有相通之处。小结Rotating the Box 是一道易读难写对的二维数组综合题考察点集中在三点能否看出旋转前先做行内落石、能否用双指针把每行落石做到线性时间、能否写对旋转坐标映射。按本文顺序掌握暴力解 → 双指针解 → 单趟合并解并在纸上用 2×3 小网格验证坐标公式就能在面试中稳定给出正确且最优的实现。九种语言的完整可运行代码都在 articles/rotating-the-box.md 中可直接对照练习。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考