跳至主要內容

1861. 旋转盒子

1861. 旋转盒子

🟠   🔖  数组 双指针 矩阵  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an m x n matrix of characters box representing a side-view of a box. Each cell of the box is one of the following:

  • A stone '#'
  • A stationary obstacle '*'
  • Empty '.'

The box is rotated 90 degrees clockwise , causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles' positions, and the inertia from the box's rotation does not affect the stones' horizontal positions.

It is guaranteed that each stone in box rests on an obstacle, another stone, or the bottom of the box.

Return ann x m matrix representing the box after the rotation described above.

Example 1:

Input: box = [["#",".","#"]]

Output: [["."], ["#"], ["#"]]

Example 2:

Input: box = [["#",".","*","."], ["#","#","*","."]]

Output: [["#","."], ["#","#"], ["*","*"], [".","."]]

Example 3:

Input: box = [["#","#","*",".","*","."], ["#","#","#","*",".","."], ["#","#","#",".","#","."]]

Output: [[".","#","#"], [".","#","#"], ["#","#","*"], ["#","*","."], ["#",".","*"], ["#",".","."]]

Constraints:

  • m == box.length
  • n == box[i].length
  • 1 <= m, n <= 500
  • box[i][j] is either '#', '*', or '.'.

题目大意

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

解题思路

  1. 要将盒子顺时针旋转 90°，本质上，这意味着第 i 行变成新数组中的第 m - 1 - i 列。旋转时需要模拟重力作用，保证石头 # 尽可能往下落，遇到障碍物 * 会停住。
  2. 初始化结果矩阵 res，大小为 n x m。
  3. 对于每一行，从右向左遍历，记录石头下落的位置：
    • 如果遇到石头 #，将其移动到当前重力作用的最右位置 bottom，并更新 bottom。
    • 如果遇到障碍物 *，将障碍物位置记录到结果矩阵，并更新重力边界 bottom 为障碍物的左边。
  4. 根据旋转逻辑，将原数组中的每个元素放到结果矩阵对应位置。
  5. 处理完成后，返回旋转后的盒子矩阵。

复杂度分析

  • 时间复杂度：O(m * n)，需要遍历矩阵里的每个元素。
  • 空间复杂度：O(m * n)，结果矩阵 res 占用O(m * n)的空间。

代码

/**
 * @param {character[][]} box
 * @return {character[][]}
 */
var rotateTheBox = function (box) {
	// m 行，n 列
	const m = box.length,
		n = box[0].length;

	// 初始化结果矩阵
	let res = Array(n)
		.fill()
		.map(() => Array(m).fill('.'));

	for (let row = 0; row < m; row++) {
		let bottom = n - 1; // 记录石头下落的最右位置
		for (let col = n - 1; col >= 0; col--) {
			if (box[row][col] == '#') {
				// 遇到石头
				res[bottom--][m - 1 - row] = '#'; // 放到当前最右位置
			} else if (box[row][col] == '*') {
				// 遇到障碍物
				res[col][m - 1 - row] = '*'; // 放置障碍物
				bottom = col - 1; // 更新重力边界
			}
		}
	}

	// 返回旋转后的矩阵
	return res;
};
Copyright © 2024 2xiao