LeetCode 54. 螺旋矩阵

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 54. 螺旋矩阵

思路分析

定义四个边界：top、bottom、left 和 right，分别表示当前可遍历的矩阵的上下左右边界。

使用一个循环，按照顺时针的顺序遍历矩阵：

从左到右遍历 top 行，然后 top 边界下移。

从上到下遍历 right 列，然后 right 边界左移。

从右到左遍历 bottom 行（如果 top 仍然小于等于 bottom），然后 bottom 边界上移。

从下到上遍历 left 列（如果 left 仍然小于等于 right），然后 left 边界右移。

重复以上步骤，直到所有元素都被遍历。

参考代码

func spiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 {
		return []int{}
	}

	var res []int
	top, bottom := 0, len(matrix)-1
	left, right := 0, len(matrix[0])-1

	for top <= bottom && left <= right {
		// 从左到右遍历 top 行
		for i := left; i <= right; i++ {
			res = append(res, matrix[top][i])
		}
		top++

		// 从上到下遍历 right 列
		for i := top; i <= bottom; i++ {
			res = append(res, matrix[i][right])
		}
		right--

		// 从右到左遍历 bottom 行
		if top <= bottom {
			for i := right; i >= left; i-- {
				res = append(res, matrix[bottom][i])
			}
			bottom--
		}

		// 从下到上遍历 left 列
		if left <= right {
			for i := bottom; i >= top; i-- {
				res = append(res, matrix[i][left])
			}
			left++
		}
	}

	return res
}

时间复杂度：O (m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们遍历了每个元素一次。

空间复杂度：O (1)，不考虑输出结果的空间，使用了常数级别的额外空间。

🍏 点击查看 Java 题解

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        int rowBegin = 0, rowEnd = m - 1;
        int colBegin = 0, colEnd = n - 1;

        while (rowBegin <= rowEnd && colBegin <= colEnd) {
            // 向右
            for (int j = colBegin; j <= colEnd; j++) {
                res.add(matrix[rowBegin][j]);
            }
            rowBegin++;

            // 向下
            for (int i = rowBegin; i <= rowEnd; i++) {
                res.add(matrix[i][colEnd]);
            }
            colEnd--;

            // 向左（检查是否需要继续）
            if (rowBegin <= rowEnd) {
                for (int j = colEnd; j >= colBegin; j--) {
                    res.add(matrix[rowEnd][j]);
                }
                rowEnd--;
            }

            // 向上（检查是否需要继续）
            if (colBegin <= colEnd) {
                for (int i = rowEnd; i >= rowBegin; i--) {
                    res.add(matrix[i][colBegin]);
                }
                colBegin++;
            }
        }
        return res;
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/76110162