golang 解法, 执行用时: 368 ms, 内存消耗: 10.7 MB, 提交时间: 2022-11-29 12:08:37

func rotateTheBox(a [][]byte) [][]byte {
	n, m := len(a), len(a[0])
	ans := make([][]byte, m)
	for i := range ans {
		ans[i] = make([]byte, n)
		for j := range ans[i] {
			ans[i][j] = '.'
		}
	}
	for i, r := range a {
		for j := 0; j < m; j++ {
			c := 0
			// 注意这里 j 和外层循环的 j 是同一个变量，因此时间复杂度为 O(nm)
			for ; j < m && r[j] != '*'; j++ {
				if r[j] == '#' {
					c++
				}
			}
			if j < m {
				ans[j][n-1-i] = '*'
			}
			for k := j - 1; c > 0; k-- {
				ans[k][n-1-i] = '#'
				c--
			}
		}
	}
	return ans
}

java 解法, 执行用时: 7 ms, 内存消耗: 76 MB, 提交时间: 2022-11-29 12:08:18

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        char[][] ans = new char[n][m];  // 用来构建返回值的二维数组
        // 首先逐行处理，把石头挪到该放的地方去
        for (int i = 0; i < m; ++i) {
            // 首先假设当前 i 行可放的位置是 pos
            int pos = n - 1;
            // 然后从右往左遍历，逐个更新石头的位置
            for (int j = n - 1; j >= 0; --j) {
                if (box[i][j] == '#') {
                    // 遇到了石头，先把它放到该放的位置去
                    box[i][pos--] = '#';
                    // 确保没有覆盖掉起始位置的石头，然后把挪动前的位置置为 空（.）
                    if (pos != j - 1) box[i][j] = '.';
                }
                // 如果遇到了障碍物，那么就更新可放的位置为障碍物的下一个位置（左边）
                else if (box[i][j] == '*') pos = j - 1;

            }
        }
        // 然后把更新后的位置映射到返回值中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[j][m - 1 - i] = box[i][j];
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 340 ms, 内存消耗: 52.1 MB, 提交时间: 2022-11-29 12:07:48

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        m, n = len(box), len(box[0])

        for i in range(m):
            # 队首对应的位置
            front_pos = n - 1
            for j in range(n - 1, -1, -1):
                if box[i][j] == "*":
                    # 遇到障碍物，清空队列
                    front_pos = j - 1
                elif box[i][j] == "#":
                    if front_pos > j:
                        # 如果队列不为空，石头就会下落
                        box[i][front_pos] = "#"
                        box[i][j] = "."
                        front_pos -= 1
                    else:
                        front_pos = j - 1

        # 将矩阵顺时针旋转 90 度放入答案
        ans = [[""] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                ans[j][m - i - 1] = box[i][j]
        return ans

python3 解法, 执行用时: 428 ms, 内存消耗: 52 MB, 提交时间: 2022-11-29 12:07:24

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        m, n = len(box), len(box[0])

        for i in range(m):
            q = deque()
            for j in range(n - 1, -1, -1):
                if box[i][j] == "*":
                    # 遇到障碍物，清空队列
                    q.clear()
                elif box[i][j] == "#":
                    if q:
                        # 如果队列不为空，石头就会下落
                        pos = q.popleft()
                        box[i][pos] = "#"
                        box[i][j] = "."
                        # 由于下落，石头变为空位，也需要加入队列
                        q.append(j)
                else:
                    # 将空位加入队列
                    q.append(j)

        # 将矩阵顺时针旋转 90 度放入答案
        ans = [[""] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                ans[j][m - i - 1] = box[i][j]
        return ans