LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.06
• 题目：1861. 旋转盒子
• 难度：中等
• 标签：数组、矩阵、双指针

1. 题目理解

问题描述：
给你一个 m x n 的字符矩阵 boxGrid，表示盒子的侧视图。矩阵元素含义：

• '#'：石头
• '*'：固定障碍物
• '.'：空位置

将盒子顺时针旋转90度，由于重力影响，石头会垂直掉落，直到碰到障碍物、其他石头或盒子底部。障碍物位置固定不变，石头水平位置不会改变。初始状态保证石头都稳定在障碍物、其他石头或盒子底部上。返回旋转后的 n x m 矩阵。

示例：

输入：boxGrid = [["#",".","#"]] 输出：[["."], ["#"], ["#"]] 解释：原矩阵为一行三列，顺时针旋转90度后变为三行一列。重力作用下，两个石头掉落到底部，形成从上到下 .、#、# 的结果。

2. 解题思路

核心观察

• 问题可拆分为两步：先完成矩阵的顺时针旋转90度，再处理重力导致的石头掉落；
• 顺时针旋转90度后，原矩阵的行变为新矩阵的列，原矩阵的列变为新矩阵的逆序行；
• 重力作用下，石头只会沿列向下移动，因此可对每一列从下往上处理，模拟石头掉落过程；
• 障碍物是天然的“分界点”，石头无法穿过障碍物，因此可分段处理每一列的不同区域。

算法步骤

1. 矩阵旋转：创建 n x m 的结果矩阵，按顺时针90度旋转规则填充元素：res[j][m-i-1] = boxGrid[i][j]；
2. 模拟重力掉落：
   • 对结果矩阵的每一列，从下往上遍历；
   • 遇到空位时，向上寻找最近的石头或障碍物；
   • 找到石头则交换位置，找到障碍物则停止当前区域的处理；
3. 返回结果矩阵。

3. 代码实现

package lc1861;
class lc3600_lc3699.lc3660.Solution {
    public char[][] rotateTheBox(char[][] boxGrid) {
        int m = boxGrid.length;
        int n = boxGrid[0].length;
        char[][] res = new char[n][m];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                res[j][m-i-1] = boxGrid[i][j];
            }
        }
        for(int i = n-1; i >= 0; i--){
            for (int j = m-1; j >=0 ; j--) {
                if (res[i][j]=='.'){
                    int k = i;
                    while (k>=0){
                        if (res[k][j]=='#'){
                            res[k][j] = '.';
                            res[i][j] = '#';
                            break;
                        }
                        if (res[k][j]=='*'){break;}
                        k--;
                    }
                }
            }
        }
        return  res;
    }
}

4. 代码优化说明

优化点1：双指针法模拟掉落（消除嵌套循环）

对每一列，用一个指针记录当前可放置石头的位置，从下往上遍历，遇到石头则直接放到可放置位置，遇到障碍物则重置指针：

for (int col = 0; col < m; col++) {
    int write = n - 1;
    for (int row = n - 1; row >= 0; row--) {
        if (res[row][col] == '*') {
            write = row - 1;
        } else if (res[row][col] == '#') {
            res[row][col] = '.';
            res[write--][col] = '#';
        }
    }
}

优化点2：旋转与掉落合并处理（可选）

可在原矩阵上先模拟重力，再旋转矩阵，减少空间开销，但逻辑复杂度会略有增加。

5. 复杂度分析

• 时间复杂度：$O(m\times n)$

  • 矩阵旋转：$O(m\times n)$；
  • 模拟重力：优化后双指针法为 $O(m\times n)$，原嵌套循环法最坏为 $O(m\times n^2)$，优化后可降为线性级。

• 空间复杂度：$O(m\times n)$

  • 需创建 n x m 的结果矩阵存储旋转后的盒子状态。

6. 总结

• 核心思路是矩阵旋转 + 重力模拟，将问题拆分为两个独立步骤处理；
• 关键技巧：利用双指针法优化石头掉落的模拟过程，避免嵌套循环导致的高时间复杂度；
• 障碍物的存在天然分割了列，分段处理每一列的石头掉落，可进一步提升效率。

关键点回顾

1. 顺时针旋转90度的矩阵变换规则：res[j][m-i-1] = boxGrid[i][j]；
2. 重力作用下石头沿列向下掉落，需按列处理；
3. 双指针法是模拟掉落的最优方式，可将时间复杂度优化至线性级。