What is the core pattern for Rotating the Box?

The problem uses two-pointer scanning with invariant tracking per row to simulate stones falling under gravity after rotation.

How do I rotate a matrix 90 degrees clockwise?

Use the mapping rotatedBox[i][j] = box[m - 1 - j][i] to transform the original box positions correctly.

Can obstacles move during the rotation?

No, obstacles remain fixed in their original positions and only stones fall due to gravity.

Why use two pointers instead of single iteration?

Two pointers allow tracking empty spaces and stones efficiently per row, preventing overwriting stones and reducing complexity to O(m*n).

What if the box has maximum size 500x500?

The two-pointer approach ensures O(m*n) time complexity, making it feasible to handle large grids within constraints.

#1861

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

旋转盒子

给你一个 m x n 的字符矩阵 boxGrid ，它表示一个箱子的侧视图。箱子的每一个格子可能为： '#' 表示石头 '*' 表示固定的障碍物 '.' 表示空位置这个箱子被顺时针旋转 90 度，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的…

数组双指针矩阵

题目描述

给你一个 m x n 的字符矩阵 boxGrid ，它表示一个箱子的侧视图。箱子的每一个格子可能为：

'#' 表示石头
'*' 表示固定的障碍物
'.' 表示空位置

这个箱子被 顺时针旋转 90 度 ，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。重力不会影响障碍物的位置，同时箱子旋转不会产生惯性，也就是说石头的水平位置不会发生改变。

题目保证初始时 boxGrid 中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。

请你返回一个 n x m 的矩阵，表示按照上述旋转后，箱子内的结果。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

m == boxGrid.length
n == boxGrid[i].length
1 <= m, n <= 500
boxGrid[i][j] 只可能是 '#' ，'*' 或者 '.' 。

lightbulb

解题思路

方法一：队列模拟

我们先将矩阵顺时针旋转 90 度，然后模拟每一列石头的下落过程。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        m, n = len(box), len(box[0])
        ans = [[None] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                ans[j][m - i - 1] = box[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

speed

复杂度分析

指标	值
时间	complexity is O(m \times n) because every cell is scanned once for rotation and once for gravity simulation. Space complexity is O(m \times n) for storing the rotated box matrix separate from the original grid.
空间	O(m \times n)

psychology

面试官常问的追问

外企场景

question_mark
Are you tracking empty spaces and obstacles efficiently per row?
question_mark
Can you explain how rotatedBox[i][j] = box[m - 1 - j][i] ensures correct clockwise rotation?
question_mark
Do you understand why two pointers are needed instead of moving stones one by one?

warning

常见陷阱

外企场景

error
Forgetting to reset the empty-space pointer after an obstacle in a row, causing incorrect stone placement.
error
Rotating before simulating gravity can produce wrong final positions.
error
Using nested loops per stone without two-pointer scanning can exceed O(m*n) time and fail for large grids.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Rotate counterclockwise with similar gravity rules, adjusting indices accordingly.
arrow_right_alt
Allow diagonal gravity where stones can slide to lower adjacent empty cells.
arrow_right_alt
Change obstacles to movable blocks that can fall, requiring different invariant tracking.

help

常见问题

外企场景

继续练习

#2503 矩阵查询可获得的最大分数 #1855 下标对中的最大距离 #1877 数组中最大数对和的最小值