旋转盒子
难度:
标签:
题目描述
给你一个 m x n 的字符矩阵 box ，它表示一个箱子的侧视图。箱子的每一个格子可能为：
'#'表示石头'*'表示固定的障碍物'.'表示空位置
这个箱子被 顺时针旋转 90 度 ，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。重力 不会 影响障碍物的位置，同时箱子旋转不会产生惯性 ，也就是说石头的水平位置不会发生改变。
题目保证初始时 box 中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。
请你返回一个 n x m的矩阵，表示按照上述旋转后，箱子内的结果。
示例 1：
输入：box = [["#",".","#"]] 输出：[["."], ["#"], ["#"]]
示例 2：
输入：box = [["#",".","*","."], ["#","#","*","."]] 输出：[["#","."], ["#","#"], ["*","*"], [".","."]]
示例 3：
输入：box = [["#","#","*",".","*","."], ["#","#","#","*",".","."], ["#","#","#",".","#","."]] 输出：[[".","#","#"], [".","#","#"], ["#","#","*"], ["#","*","."], ["#",".","*"], ["#",".","."]]
提示：
m == box.lengthn == box[i].length1 <= m, n <= 500box[i][j]只可能是'#'，'*'或者'.'。
代码结果
运行时间: 150 ms, 内存: 59.5 MB
/*
题目思路:
1. 利用Java Stream对二维数组进行行列转换。
2. 使用Stream的map和collect方法处理每一行和列。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public char[][] rotateTheBox(char[][] box) {
int m = box.length;
int n = box[0].length;
return IntStream.range(0, n)
.mapToObj(j -> IntStream.range(0, m)
.mapToObj(i -> box[i][n - 1 - j])
.collect(Collectors.toCollection(ArrayList::new)))
.map(this::applyGravity)
.toArray(char[][]::new);
}
private char[] applyGravity(ArrayList<Character> list) {
int emptyPos = list.size() - 1;
char[] result = new char[list.size()];
Arrays.fill(result, '.');
for (int i = list.size() - 1; i >= 0; i--) {
char c = list.get(i);
if (c == '*') {
emptyPos = i - 1;
result[i] = '*';
} else if (c == '#') {
result[emptyPos--] = '#';
}
}
return result;
}
}解释
方法:
题解首先确定了原矩阵的行数 m 和列数 n。接着，创建一个新矩阵 new_box，其尺寸为 n x m，初始填充为 '.'，以匹配旋转后的盒子结构。算法从左到右遍历原始矩阵的每一行，对于每一行，从右到左处理每个元素，模拟重力效应。如果遇到石头 ('#')，将它放置在当前列的最低可用位置（由变量 count 控制）。如果遇到障碍物 ('*')，将障碍物放在新矩阵的对应位置，并重置 count 为障碍物上方的位置。每处理完一行后，count 重置为列的底部，即 y-1，为下一行做准备。这样，按列处理完所有行之后，得到的 new_box 即为所求的旋转后矩阵。
时间复杂度:
O(m*n)
空间复杂度:
O(n*m)
代码细节讲解
🦆
在处理石头和障碍物时，代码中为什么选择从右向左遍历每一行？这样的遍历方向有何优势？
▷🦆
既然石头只会垂直下落，新矩阵中的某一列的计数（count）是如何确保石头正确堆叠而不会覆盖已存在的石头或障碍物的？
▷🦆
如何处理最底部的石头和障碍物，特别是当它们在最后一行时？
▷🦆
如果原始矩阵的某一行全是空位（'.'），算法中对这种情况的处理是否会影响效率，有没有更优化的处理方式？
▷