【数据结构与算法】力扣 54. 螺旋矩阵

问题描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入： matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出： [1,2,3,6,9,8,7,4,5]

示例 2：

输入： matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出： [1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

分析解答

• 定义四个边界：

  • top 表示当前上边界，初始为 0。
  • bottom 表示当前下边界，初始为 m - 1。
  • left 表示当前左边界，初始为 0。
  • right 表示当前右边界，初始为 n - 1。

• 循环遍历矩阵：

  • 从左到右遍历顶部边界，然后将 top 下移。
  • 从上到下遍历右边界，然后将 right 左移。
  • 从右到左遍历底部边界（如果还没有遍历过），然后将 bottom 上移。
  • 从下到上遍历左边界（如果还没有遍历过），然后将 left 右移。

function spiralOrder(matrix) {if (matrix.length === 0) return [];const result = [];let top = 0, bottom = matrix.length - 1;let left = 0, right = matrix[0].length - 1;while (top <= bottom && left <= right) {// 从左到右遍历顶部for (let i = left; i <= right; i++) {result.push(matrix[top][i]);}top++;// 从上到下遍历右边界for (let i = top; i <= bottom; i++) {result.push(matrix[i][right]);}right--;// 从右到左遍历底部if (top <= bottom) {for (let i = right; i >= left; i--) {result.push(matrix[bottom][i]);}bottom--;}// 从下到上遍历左边界if (left <= right) {for (let i = bottom; i >= top; i--) {result.push(matrix[i][left]);}left++;}}return result;
}// 测试示例
console.log(spiralOrder([[1,2,3],[4,5,6],[7,8,9]])); // 输出: [1,2,3,6,9,8,7,4,5]
console.log(spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12]])); // 输出: [1,2,3,4,8,12,11,10,9,5,6,7]

遍历矩阵：

• 按顺时针顺序依次遍历上、右、下、左四个边界，将对应的元素添加到结果数组中。
• 每遍历完一个边界，就缩小对应的边界值，逐渐向内层推进。
• 使用条件判断来避免重复遍历同一行或同一列。

if (top <= bottom) 和 if (left <= right) 的作用：

1. if (top <= bottom) 的作用：

   • 当从左到右遍历完 top 行，以及从上到下遍历完 right 列后，会将 bottom 行从右到左遍历。
   • 然而，有可能在遍历 top 行之后，top 已经超过了 bottom（说明已经没有未遍历的行），所以需要先判断 top <= bottom 是否成立。如果不成立，说明不需要再遍历 bottom 行，避免重复处理。

2. if (left <= right) 的作用：

   • 当从右到左遍历完 bottom 行后，会将 left 列从下到上遍历。
   • 同理，如果在遍历 right 列之后，left 已经超过了 right（说明已经没有未遍历的列），那么就不需要再遍历 left 列。因此，先判断 left <= right 是否成立。

复杂度分析

• 时间复杂度：O(m×n)O(m \times n)O(m×n)，因为每个元素会被访问一次。
• 空间复杂度：O(1)O(1)O(1)，除了返回结果外，额外使用的空间是常数级别。

思路拓展