1861.旋转盒子：模拟(双指针)

【LetMeFly】1861.旋转盒子：模拟(双指针)

力扣题目链接：https://leetcode.cn/problems/rotating-the-box/

给你一个 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] 只可能是 '#' ，'*' 或者 '.' 。

解题方法：先向右，后旋转

首先让盒子里面的所有石头尽可能右移，然后把矩阵顺时针旋转90°C。

石头右移

一行一行地处理。

双指针，一个指针指向起始位置，一个指针向右移动，移动过程中记录一共多少石头。

当右指针遇到障碍或移出盒子，则从新分配这片连通区域的石头(先数个空格子、后数个石头)。

矩阵旋转

令$ans[n - i - 1] = boxGrid[i][j]$即可。

时空复杂度

• 时间复杂度$O(mn)$
• 空间复杂度$O(1)$，力扣返回值不计入算法空间复杂度

AC代码

C++

/*
 * @LastEditTime: 2026-05-06 20:02:37
 */
class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int n = boxGrid.size(), m = boxGrid[0].size();
        for (int i = 0; i < n; i++) {
            for (int start = 0, now = 0, cnt = 0; now <= m; now++) {
                if (now == m || boxGrid[i][now] == '*') {  // 障碍
                    int empty = now - start - cnt;
                    for (int j = start; j < start + empty; j++) {
                        boxGrid[i][j] = '.';
                    }
                    for (int j = start + empty; j < now; j++) {
                        boxGrid[i][j] = '#';
                    }
                    start = now + 1;
                    cnt = 0;
                } else {
                    cnt += boxGrid[i][now] == '#';
                }
            }
        }

        vector<vector<char>> ans(m, vector<char>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[j][n - i - 1] = boxGrid[i][j];
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源