企业官网建设流程全解析

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. 代码实现

packagelc1861;classSolution{publicchar[][]rotateTheBox(char[][]boxGrid){intm=boxGrid.length;intn=boxGrid[0].length;char[][]res=newchar[n][m];for(inti=0;i<m;i++){for(intj=0;j<n;j++){res[j][m-i-1]=boxGrid[i][j];}}for(inti=n-1;i>=0;i--){for(intj=m-1;j>=0;j--){if(res[i][j]=='.'){intk=i;while(k>=0){if(res[k][j]=='#'){res[k][j]='.';res[i][j]='#';break;}if(res[k][j]=='*'){break;}k--;}}}}returnres;}}

4. 代码优化说明

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

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

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

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

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

5. 复杂度分析

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

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

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

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

6. 总结

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

关键点回顾

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