LeetCode 1861中等双指针 · 滑窗

旋转盒子图解题解

这道题到底在问什么

给你一个 m 行 n 列的字符矩阵 box,井号是石头,星号是固定障碍物,点是空位。把箱子顺时针旋转 90 度,由于重力,石头会垂直下落,直到落在障碍物、别的石头或箱子底部为止;障碍物不动,石头的水平位置在旋转前不变。请返回旋转后的 n 行 m 列矩阵。

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

最优解：一步一步想明白

3记牢这两步:先让每行石头向右靠拢、遇障碍物断开,再把整张图顺时针旋转。下面每一帧都在套这两步,先从第一行的靠拢开始。
4红 = 障碍物(不动),蓝底 = 待处理石头这就是 2 行 4 列的箱子,井号是石头,星号是障碍物,点是空位。咱们先一行一行让石头向右靠拢。右边面板记这一行右侧有哪些空位能落脚,现在从行 0 开始,从最右边往左扫。
5记下一个可落脚的空位行 0 扫到第 3 列,是空位。把它记进右边面板,当作后面石头可以滑过来的落脚点。现在这一行右侧能落脚的空位有 1 个。
6障碍物挡住去路,落脚点清空行 0 扫到第 2 列,是障碍物星号。石头穿不过障碍物,所以障碍物右边攒下的落脚点在这里全部作废,面板清空。障碍物左边的石头只能落在障碍物这一侧,和右边互不相通。
7记下一个可落脚的空位行 0 扫到第 1 列,是空位。把它记进右边面板,当作后面石头可以滑过来的落脚点。现在这一行右侧能落脚的空位有 1 个。
8右边第 1 列有空位,石头滑过去行 0 扫到第 0 列,是一颗石头。它右边最近的空位在第 1 列。重力让它向右滑,它要从第 0 列滚到第 1 列去。
9第 0 列空出来,成为新落脚点石头落在第 1 列,原来的第 0 列空了出来。这个新腾出的空位接着记进面板,留给它左边可能还有的石头用。
10本行:. # * .行 0 靠拢完成,石头都贴到了障碍物左边。原来它散在第 0 列,现在滑到了第 1 列,紧挨着障碍物。接着处理行 1。
11记下一个可落脚的空位行 1 扫到第 3 列,是空位。把它记进右边面板,当作后面石头可以滑过来的落脚点。现在这一行右侧能落脚的空位有 1 个。
12障碍物挡住去路,落脚点清空行 1 扫到第 2 列,是障碍物星号。石头穿不过障碍物,所以障碍物右边攒下的落脚点在这里全部作废,面板清空。障碍物左边的石头只能落在障碍物这一侧,和右边互不相通。
13右侧没有空位,石头原地不动行 1 扫到第 1 列,是一颗石头,它右边马上就是障碍物,同一段里没有可落脚的空位,所以它已经靠到位,原地不动。
14右侧没有空位,石头原地不动行 1 扫到第 0 列,是一颗石头,它右边同一段内已被第 1 列石头占住,再往右被障碍物截断,没有可用的落脚点,它已经靠到位,原地不动。
15本行:# # * .行 1 靠拢完成。这一行的两颗石头本来就贴着障碍物,障碍物左侧这一段没有空位;第 3 列虽然是空位,却被障碍物隔开,给不了左侧的石头用,所以两颗石头原地没动。两行都靠拢好了。
16重力已在旋转前先「模拟」到位两行的石头都向右靠拢好了。为什么可以在旋转前就这么做?因为顺时针转 90 度之后,原来的向右恰好变成向下,旋转后石头往下掉,等价于旋转前让它们先向右滑到位。现在只剩纯粹的旋转这一步了。
17底行将变左列,顶行将变右列开始旋转。顺时针转 90 度有个好记的规律:原来的底行,会变成结果的左列;原来的顶行,会变成结果的右列。这里先把底行,也就是行 1 的这四个格子高亮出来,它们待会儿会竖着排到结果的最左边一列。
18放入石头(井号)底行从左往右第 0 个是石头(井号),顺时针转过去,它落到结果左列从上往下第 0 行。继续放下一个。
19放入石头(井号)底行从左往右第 1 个是石头(井号),顺时针转过去,它落到结果左列从上往下第 1 行。继续放下一个。
20放入障碍物(星号)底行从左往右第 2 个是障碍物(星号),顺时针转过去,它落到结果左列从上往下第 2 行。继续放下一个。
21放入空位(点)底行从左往右第 3 个是空位(点),顺时针转过去,它落到结果左列从上往下第 3 行。结果的左列这就填满了。
22左列 = 底行竖过来结果的左列填好了,从上到下是石头、石头、障碍、空,正是原来底行从左到右的顺序竖过来。接着把顶行,也就是行 0,放到结果的右列。
23放入空位(点)顶行从左往右第 0 个是空位(点),顺时针转过去,它落到结果右列从上往下第 0 行。继续放下一个。
24放入石头(井号)顶行从左往右第 1 个是石头(井号),顺时针转过去,它落到结果右列从上往下第 1 行。继续放下一个。
25放入障碍物(星号)顶行从左往右第 2 个是障碍物(星号),顺时针转过去,它落到结果右列从上往下第 2 行。继续放下一个。
26放入空位(点)顶行从左往右第 3 个是空位(点),顺时针转过去,它落到结果右列从上往下第 3 行。结果的右列也填满了。
27答案 = 每行靠拢 + 顺时针旋转整张图转完了,结果是 4 行 2 列。回看全程,咱们没有真的去转图,而是先让每行石头向右靠拢模拟掉落,再按顺时针把底行变左列、顶行变右列排好。这个结果和题目样例 2 给的答案一模一样。

⚠️ 容易写错的地方

✗ 错：让石头穿过障碍物继续下落

✓ 对：障碍物星号是死挡板,石头只能停在它这一侧

扫到障碍物必须把攒下的落脚点全部清空,障碍物两侧的空位不能通用

✗ 错：搞反旋转后重力的方向

✓ 对：顺时针转 90 度后,原来的向右变成向下

正因如此才能在旋转前先让每行向右靠拢来模拟下落,方向记反结果就全错

✗ 错：把结果矩阵的行列尺寸写反

✓ 对：原来 m 行 n 列,旋转后是 n 行 m 列

行列互换了,先开对 n 行 m 列的新数组,再往里填,别沿用原尺寸

✗ 错：原地在同一个矩阵上转

✓ 对：旋转后行列尺寸变了,要另开新数组

除非矩阵是正方形,否则没法原地旋转,老老实实新建 n 行 m 列的 ans

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int m = boxGrid.size(), n = boxGrid[0].size();
        vector<vector<char>> ans(n, vector<char>(m));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[j][m - i - 1] = boxGrid[i][j];
            }
        }
        for (int j = 0; j < m; ++j) {
            queue<int> q;
            for (int i = n - 1; ~i; --i) {
                if (ans[i][j] == '*') {
                    queue<int> t;
                    swap(t, q);
                } else if (ans[i][j] == '.') {
                    q.push(i);
                } else if (!q.empty()) {
                    ans[q.front()][j] = '#';
                    q.pop();
                    ans[i][j] = '.';
                    q.push(i);
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public char[][] rotateTheBox(char[][] boxGrid) {
        int m = boxGrid.length, n = boxGrid[0].length;
        char[][] ans = new char[n][m];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[j][m - i - 1] = boxGrid[i][j];
            }
        }
        for (int j = 0; j < m; ++j) {
            Deque<Integer> q = new ArrayDeque<>();
            for (int i = n - 1; i >= 0; --i) {
                if (ans[i][j] == '*') {
                    q.clear();
                } else if (ans[i][j] == '.') {
                    q.offer(i);
                } else if (!q.isEmpty()) {
                    ans[q.pollFirst()][j] = '#';
                    ans[i][j] = '.';
                    q.offer(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))

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着旋转盒子的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么可以先靠拢再旋转,和先旋转再让石头下落结果一样?+

关键在于旋转把方向也带着转了。顺时针转 90 度后,原图里的向右这个方向,恰好对应到新图里的向下。参考代码是先把图转过去,再让石头在新图里沿着向下的方向掉;动画是不转图、先让石头在原图里沿着向右的方向滑到位,再把已经靠拢好的图整体转过去。同一批石头、同样的相对位置、同样被障碍物挡着,只是操作顺序前后交换了,最终每颗石头落在哪个格子完全一致,所以两种做法等价。

每行靠拢那一步,能不能不用队列,用两个指针原地做?+

可以。对每一行从右往左扫,维护一个写指针,一开始指向最右的可落位置。往左遇到障碍物,就把写指针跳到障碍物左边一格重新开始;遇到空位不管它;遇到石头,就把石头写到写指针处、写指针再左移一格,如果石头本来就在写指针处就相当于没动。这样一趟扫下来,石头都紧贴右侧或障碍物排好,只用了常数个额外变量,不必开队列。用队列只是把空位显式记下来更好讲。

这题时间复杂度还能不能更低?+

不能。答案矩阵有 m 乘 n 个格子,你至少得把每个输入格子读一遍、每个输出格子写一遍,所以 O(m 乘 n) 已经是这道题的下界。旋转拷贝和逐列扫落都恰好是这个量级,已经最优,优化只能在常数上做文章,量级降不下来。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把旋转盒子一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 1861中等双指针 · 滑窗

旋转盒子图解题解

这道题到底在问什么

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

最优解：一步一步想明白

3记牢这两步:先让每行石头向右靠拢、遇障碍物断开,再把整张图顺时针旋转。下面每一帧都在套这两步,先从第一行的靠拢开始。
4红 = 障碍物(不动),蓝底 = 待处理石头这就是 2 行 4 列的箱子,井号是石头,星号是障碍物,点是空位。咱们先一行一行让石头向右靠拢。右边面板记这一行右侧有哪些空位能落脚,现在从行 0 开始,从最右边往左扫。
5记下一个可落脚的空位行 0 扫到第 3 列,是空位。把它记进右边面板,当作后面石头可以滑过来的落脚点。现在这一行右侧能落脚的空位有 1 个。
6障碍物挡住去路,落脚点清空行 0 扫到第 2 列,是障碍物星号。石头穿不过障碍物,所以障碍物右边攒下的落脚点在这里全部作废,面板清空。障碍物左边的石头只能落在障碍物这一侧,和右边互不相通。
7记下一个可落脚的空位行 0 扫到第 1 列,是空位。把它记进右边面板,当作后面石头可以滑过来的落脚点。现在这一行右侧能落脚的空位有 1 个。
8右边第 1 列有空位,石头滑过去行 0 扫到第 0 列,是一颗石头。它右边最近的空位在第 1 列。重力让它向右滑,它要从第 0 列滚到第 1 列去。
9第 0 列空出来,成为新落脚点石头落在第 1 列,原来的第 0 列空了出来。这个新腾出的空位接着记进面板,留给它左边可能还有的石头用。
10本行:. # * .行 0 靠拢完成,石头都贴到了障碍物左边。原来它散在第 0 列,现在滑到了第 1 列,紧挨着障碍物。接着处理行 1。
11记下一个可落脚的空位行 1 扫到第 3 列,是空位。把它记进右边面板,当作后面石头可以滑过来的落脚点。现在这一行右侧能落脚的空位有 1 个。
12障碍物挡住去路,落脚点清空行 1 扫到第 2 列,是障碍物星号。石头穿不过障碍物,所以障碍物右边攒下的落脚点在这里全部作废,面板清空。障碍物左边的石头只能落在障碍物这一侧,和右边互不相通。
13右侧没有空位,石头原地不动行 1 扫到第 1 列,是一颗石头,它右边马上就是障碍物,同一段里没有可落脚的空位,所以它已经靠到位,原地不动。
14右侧没有空位,石头原地不动行 1 扫到第 0 列,是一颗石头,它右边同一段内已被第 1 列石头占住,再往右被障碍物截断,没有可用的落脚点,它已经靠到位,原地不动。
15本行:# # * .行 1 靠拢完成。这一行的两颗石头本来就贴着障碍物,障碍物左侧这一段没有空位;第 3 列虽然是空位,却被障碍物隔开,给不了左侧的石头用,所以两颗石头原地没动。两行都靠拢好了。
16重力已在旋转前先「模拟」到位两行的石头都向右靠拢好了。为什么可以在旋转前就这么做?因为顺时针转 90 度之后,原来的向右恰好变成向下,旋转后石头往下掉,等价于旋转前让它们先向右滑到位。现在只剩纯粹的旋转这一步了。
17底行将变左列,顶行将变右列开始旋转。顺时针转 90 度有个好记的规律:原来的底行,会变成结果的左列;原来的顶行,会变成结果的右列。这里先把底行,也就是行 1 的这四个格子高亮出来,它们待会儿会竖着排到结果的最左边一列。
18放入石头(井号)底行从左往右第 0 个是石头(井号),顺时针转过去,它落到结果左列从上往下第 0 行。继续放下一个。
19放入石头(井号)底行从左往右第 1 个是石头(井号),顺时针转过去,它落到结果左列从上往下第 1 行。继续放下一个。
20放入障碍物(星号)底行从左往右第 2 个是障碍物(星号),顺时针转过去,它落到结果左列从上往下第 2 行。继续放下一个。
21放入空位(点)底行从左往右第 3 个是空位(点),顺时针转过去,它落到结果左列从上往下第 3 行。结果的左列这就填满了。
22左列 = 底行竖过来结果的左列填好了,从上到下是石头、石头、障碍、空,正是原来底行从左到右的顺序竖过来。接着把顶行,也就是行 0,放到结果的右列。
23放入空位(点)顶行从左往右第 0 个是空位(点),顺时针转过去,它落到结果右列从上往下第 0 行。继续放下一个。
24放入石头(井号)顶行从左往右第 1 个是石头(井号),顺时针转过去,它落到结果右列从上往下第 1 行。继续放下一个。
25放入障碍物(星号)顶行从左往右第 2 个是障碍物(星号),顺时针转过去,它落到结果右列从上往下第 2 行。继续放下一个。
26放入空位(点)顶行从左往右第 3 个是空位(点),顺时针转过去,它落到结果右列从上往下第 3 行。结果的右列也填满了。
27答案 = 每行靠拢 + 顺时针旋转整张图转完了,结果是 4 行 2 列。回看全程,咱们没有真的去转图,而是先让每行石头向右靠拢模拟掉落,再按顺时针把底行变左列、顶行变右列排好。这个结果和题目样例 2 给的答案一模一样。

⚠️ 容易写错的地方

✗ 错：让石头穿过障碍物继续下落

✓ 对：障碍物星号是死挡板,石头只能停在它这一侧

扫到障碍物必须把攒下的落脚点全部清空,障碍物两侧的空位不能通用

✗ 错：搞反旋转后重力的方向

✓ 对：顺时针转 90 度后,原来的向右变成向下

正因如此才能在旋转前先让每行向右靠拢来模拟下落,方向记反结果就全错

✗ 错：把结果矩阵的行列尺寸写反

✓ 对：原来 m 行 n 列,旋转后是 n 行 m 列

行列互换了,先开对 n 行 m 列的新数组,再往里填,别沿用原尺寸

✗ 错：原地在同一个矩阵上转

✓ 对：旋转后行列尺寸变了,要另开新数组

除非矩阵是正方形,否则没法原地旋转,老老实实新建 n 行 m 列的 ans

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int m = boxGrid.size(), n = boxGrid[0].size();
        vector<vector<char>> ans(n, vector<char>(m));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[j][m - i - 1] = boxGrid[i][j];
            }
        }
        for (int j = 0; j < m; ++j) {
            queue<int> q;
            for (int i = n - 1; ~i; --i) {
                if (ans[i][j] == '*') {
                    queue<int> t;
                    swap(t, q);
                } else if (ans[i][j] == '.') {
                    q.push(i);
                } else if (!q.empty()) {
                    ans[q.front()][j] = '#';
                    q.pop();
                    ans[i][j] = '.';
                    q.push(i);
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public char[][] rotateTheBox(char[][] boxGrid) {
        int m = boxGrid.length, n = boxGrid[0].length;
        char[][] ans = new char[n][m];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[j][m - i - 1] = boxGrid[i][j];
            }
        }
        for (int j = 0; j < m; ++j) {
            Deque<Integer> q = new ArrayDeque<>();
            for (int i = n - 1; i >= 0; --i) {
                if (ans[i][j] == '*') {
                    q.clear();
                } else if (ans[i][j] == '.') {
                    q.offer(i);
                } else if (!q.isEmpty()) {
                    ans[q.pollFirst()][j] = '#';
                    ans[i][j] = '.';
                    q.offer(i);
                }
            }
        }
        return ans;
    }
}

复杂度

时间

O(m·n)

空间

O(m·n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着旋转盒子的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么可以先靠拢再旋转,和先旋转再让石头下落结果一样?+

每行靠拢那一步,能不能不用队列,用两个指针原地做?+

这题时间复杂度还能不能更低?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

旋转盒子 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

旋转盒子 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

旋转盒子图解题解

旋转盒子图解题解