Medium

题目描述

给你一个 m x n 的字符矩阵 boxGrid，表示一个盒子的侧视图。盒子的每个格子是下面字符中的一个：

  • 石头 ‘#’
  • 固定的障碍物 ‘*’
  • 空位 ‘.’

盒子顺时针旋转 90 度，由于重力的作用，一些石头会下落。每颗石头会下落直到碰到障碍物、另一颗石头或者盒子底部。重力不会影响障碍物的位置，盒子旋转产生的惯性不会影响石头的水平位置。

题目保证盒子中每颗石头都会落在障碍物、另一颗石头或者盒子底部。

返回一个 n x m 的矩阵，表示旋转后的盒子。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • m == boxGrid.length
  • n == boxGrid[i].length
  • 1 <= m, n <= 500
  • boxGrid[i][j] 是 ‘#’、’*’ 或者 ‘.’

解题思路

这道题需要两个步骤：

  1. 模拟重力效果：在旋转之前，先让每一行的石头受重力影响下落到最右边
  2. 顺时针旋转90度：使用矩阵旋转公式

详细思路：

首先模拟重力效果。对于每一行，我们从右往左遍历，维护一个指针指向当前可以放置石头的最右位置。当遇到石头时，将其移动到最右可用位置；当遇到障碍物时，重置可用位置为障碍物左边。

然后进行矩阵旋转。顺时针旋转90度的公式是：rotated[j][m-1-i] = original[i][j]，其中原矩阵是 m×n，旋转后是 n×m。

算法步骤：

  1. 对每一行应用重力：从右往左扫描，用双指针技术将石头移到正确位置
  2. 创建新矩阵并应用旋转公式
  3. 返回旋转后的矩阵

时间复杂度主要来自两次遍历矩阵，空间复杂度来自结果矩阵的存储。

代码实现

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int m = boxGrid.size();
        int n = boxGrid[0].size();
        
        // 模拟重力效果
        for (int i = 0; i < m; i++) {
            int writePos = n - 1; // 可以写入石头的位置
            for (int j = n - 1; j >= 0; j--) {
                if (boxGrid[i][j] == '#') {
                    boxGrid[i][writePos--] = '#';
                    if (writePos + 1 != j) {
                        boxGrid[i][j] = '.';
                    }
                } else if (boxGrid[i][j] == '*') {
                    writePos = j - 1;
                }
            }
        }
        
        // 旋转矩阵
        vector<vector<char>> result(n, vector<char>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[j][m - 1 - i] = boxGrid[i][j];
            }
        }
        
        return result;
    }
};

class Solution:
    def rotateTheBox(self, boxGrid: List[List[str]]) -> List[List[str]]:
        m, n = len(boxGrid), len(boxGrid[0])
        
        # 模拟重力效果
        for i in range(m):
            write_pos = n - 1  # 可以写入石头的位置
            for j in range(n - 1, -1, -1):
                if boxGrid[i][j] == '#':
                    boxGrid[i][write_pos] = '#'
                    if write_pos != j:
                        boxGrid[i][j] = '.'
                    write_pos -= 1
                elif boxGrid[i][j] == '*':
                    write_pos = j - 1
        
        # 旋转矩阵
        result = [['' for _ in range(m)] for _ in range(n)]
        for i in range(m):
            for j in range(n):
                result[j][m - 1 - i] = boxGrid[i][j]
        
        return result

public class Solution {
    public char[][] RotateTheBox(char[][] boxGrid) {
        int m = boxGrid.Length;
        int n = boxGrid[0].Length;
        
        // 模拟重力效果
        for (int i = 0; i < m; i++) {
            int writePos = n - 1; // 可以写入石头的位置
            for (int j = n - 1; j >= 0; j--) {
                if (boxGrid[i][j] == '#') {
                    boxGrid[i][writePos] = '#';
                    if (writePos != j) {
                        boxGrid[i][j] = '.';
                    }
                    writePos--;
                } else if (boxGrid[i][j] == '*') {
                    writePos = j - 1;
                }
            }
        }
        
        // 旋转矩阵
        char[][] result = new char[n][];
        for (int i = 0; i < n; i++) {
            result[i] = new char[m];
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[j][m - 1 - i] = boxGrid[i][j];
            }
        }
        
        return result;
    }
}

var rotateTheBox = function(boxGrid) {
    const m = boxGrid.length;
    const n = boxGrid[0].length;
    
    // Apply gravity to each row
    for (let i = 0; i < m; i++) {
        let writePos = n - 1;
        for (let j = n - 1; j >= 0; j--) {
            if (boxGrid[i][j] === '*') {
                writePos = j - 1;
            } else if (boxGrid[i][j] === '#') {
                if (j !== writePos) {
                    boxGrid[i][writePos] = '#';
                    boxGrid[i][j] = '.';
                }
                writePos--;
            }
        }
    }
    
    // Rotate 90 degrees clockwise
    const result = Array(n).fill().map(() => Array(m));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            result[j][m - 1 - i] = boxGrid[i][j];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(m × n)
空间复杂度O(m × n)
  • 时间复杂度：O(m × n)，需要遍历整个矩阵两次，一次模拟重力，一次进行旋转
  • 空间复杂度：O(m × n)，需要额外的矩阵存储旋转后的结果