[LeetCode] 1861. Rotating the Box

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 an n 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的矩阵，表示按照上述旋转后，箱子内的结果。

思路

这道题考察的是双指针和对矩阵的转换。
对于 input 矩阵的每一行，我们需要从右往左看，，在跳过障碍物的前提下，尽量把石头往右边摆放。
对于顺时针旋转 90 度这个环节，考察的是我们对矩阵坐标转换的熟悉程度。

复杂度

时间O(mn)
空间O(1) - 除output外不需要额外空间

代码

Java实现

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length;
        int n = box[0].length;
        for (int i = 0; i < m; i++) {
            int pos = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (box[i][j] == '#') {
                    box[i][pos] = '#';
                    if (j != pos) {
                        box[i][j] = '.';
                    }
                    pos--;
                } else if (box[i][j] == '*') {
                    pos = j - 1;
                }
            }
        }

        char[][] res = new char[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[j][m - 1 - i] = box[i][j];
            }
        }
        return res;
    }
}