旋转盒子

难度: Medium

给你一个 m x n 的字符矩阵 box ，它表示一个箱子的侧视图。箱子的每一个格子可能为：

'#' 表示石头
'*' 表示固定的障碍物
'.' 表示空位置

这个箱子被 顺时针旋转 90 度 ，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。重力不会影响障碍物的位置，同时箱子旋转不会产生惯性，也就是说石头的水平位置不会发生改变。

题目保证初始时 box 中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。

请你返回一个 n x m的矩阵，表示按照上述旋转后，箱子内的结果。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

m == box.length
n == box[i].length
1 <= m, n <= 500
box[i][j] 只可能是 '#' ，'*' 或者 '.' 。

Submission

运行时间: 150 ms

内存: 59.5 MB

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        x,y = len(box),len(box[0])
        new_box=[['.']*x for _ in range(y)]
        count=y-1
        for i in range(x):
            for j in range(y-1,-1,-1):
                if box[i][j]=='.':
                    continue
                elif box[i][j]=='#':
                    new_box[count][x-i-1]='#'
                    count-=1
                else:
                    new_box[j][x-i-1]='*'
                    count=j-1
            count=y-1
        return new_box

Explain

题解首先确定了原矩阵的行数 m 和列数 n。接着，创建一个新矩阵 new_box，其尺寸为 n x m，初始填充为 '.'，以匹配旋转后的盒子结构。算法从左到右遍历原始矩阵的每一行，对于每一行，从右到左处理每个元素，模拟重力效应。如果遇到石头 ('#')，将它放置在当前列的最低可用位置（由变量 count 控制）。如果遇到障碍物 ('*')，将障碍物放在新矩阵的对应位置，并重置 count 为障碍物上方的位置。每处理完一行后，count 重置为列的底部，即 y-1，为下一行做准备。这样，按列处理完所有行之后，得到的 new_box 即为所求的旋转后矩阵。

时间复杂度: O(m*n)

空间复杂度: O(n*m)

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        x, y = len(box), len(box[0])  # 获取原矩阵的行数和列数
        new_box = [['.'] * x for _ in range(y)]  # 创建新矩阵，初始化为 '.'
        count = y-1  # 初始化 count 为每列的底部位置
        for i in range(x):  # 遍历每一行
            for j in range(y - 1, -1, -1):  # 从右向左遍历每一行
                if box[i][j] == '.':  # 如果当前位置为空，则跳过
                    continue
                elif box[i][j] == '#':  # 如果是石头，则放到当前列的最低可用位置
                    new_box[count][x - i - 1] = '#'
                    count -= 1  # 更新当前列的最低可用位置
                else:  # 如果是障碍物
                    new_box[j][x - i - 1] = '*'
                    count = j - 1  # 重置 count 为障碍物上方位置
            count = y - 1  # 重置 count 为列的底部，为下一行做准备
        return new_box  # 返回结果矩阵

Explore

从右向左遍历每一行可以模拟重力效应，即当盒子旋转90度后，原本水平行的右端变成了新的底部。这样在处理时，可以确保当遇到石头时，它会直接下落到当前列的最低可用位置，这个位置是由从下向上累计的空位确定的。这种遍历方式允许算法在单次遍历中即可将石头放到正确的位置，且在遇到障碍物时，能立即处理障碍物上方的空间，重置石头的落点，从而有效模拟石头和障碍物的互动。

在算法中，每次处理一个元素（石头或障碍物）时，都会更新 count 变量，这个变量指向新矩阵中当前列的最低可用位置。当遇到石头时，石头被置于 count 指示的位置，并且 count 会递减，向上移动到下一个可用位置。遇到障碍物时，障碍物本身被放置在其对应的位置，随后 count 被重置为障碍物上方的位置。这确保了石头总是堆叠在最低可用空间，而不会覆盖之前已放置的石头或障碍物。

在算法中，每行处理开始前，count 被初始化为列的底部（y-1）。对于最后一行，算法以相同的方式处理石头和障碍物，确保所有元素都被放置在正确的位置。处理完最后一个元素后，不需要特别的额外处理，因为每个元素的位置都已由遍历逻辑正确确定。这意味着最底部的石头和障碍物自然按预期方式处理，无需额外逻辑。

如果某一行全是空位，当前算法仍然会遍历这一行的每个位置，尽管这些位置不会对结果矩阵产生任何影响。这种情况下的处理确实会稍微降低效率，因为进行了不必要的遍历。为了优化，可以在遍历前检查每一行是否全为空位置，如果是，则跳过该行的遍历。这样可以减少不必要的操作，提升算法的整体效率。