Medium

题目描述

给你一个 m x 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

解题思路

解题思路

这道题要求按螺旋顺序遍历矩阵，核心思想是模拟螺旋过程。

方法一：边界收缩法（推荐）

螺旋遍历的规律是：右 → 下 → 左 → 上 循环进行，每完成一个方向的遍历就收缩对应的边界。

具体步骤：

  1. 定义四个边界：上边界 top、下边界 bottom、左边界 left、右边界 right
  2. 按照顺序遍历：
    • 向右：从 left 到 right，遍历 top 行，然后 top++
    • 向下：从 top 到 bottom，遍历 right 列，然后 right--
    • 向左：从 right 到 left，遍历 bottom 行，然后 bottom--
    • 向上：从 bottom 到 top，遍历 left 列，然后 left++
  3. 每次遍历完一个方向后，检查是否还有未访问的元素

方法二：方向数组法

使用方向数组 directions = [[0,1], [1,0], [0,-1], [-1,0]] 表示右、下、左、上四个方向，配合访问标记数组，当遇到边界或已访问元素时转向。

边界收缩法更加直观且空间效率更高，是推荐解法。

代码实现

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        if (matrix.empty() || matrix[0].empty()) return result;
        
        int m = matrix.size(), n = matrix[0].size();
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        
        while (top <= bottom && left <= right) {
            // 向右遍历
            for (int j = left; j <= right; j++) {
                result.push_back(matrix[top][j]);
            }
            top++;
            
            // 向下遍历
            for (int i = top; i <= bottom; i++) {
                result.push_back(matrix[i][right]);
            }
            right--;
            
            // 向左遍历（需要检查是否还有行）
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    result.push_back(matrix[bottom][j]);
                }
                bottom--;
            }
            
            // 向上遍历（需要检查是否还有列）
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.push_back(matrix[i][left]);
                }
                left++;
            }
        }
        
        return result;
    }
};

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []
        
        result = []
        m, n = len(matrix), len(matrix[0])
        top, bottom, left, right = 0, m - 1, 0, n - 1
        
        while top <= bottom and left <= right:
            # 向右遍历
            for j in range(left, right + 1):
                result.append(matrix[top][j])
            top += 1
            
            # 向下遍历
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1
            
            # 向左遍历（需要检查是否还有行）
            if top <= bottom:
                for j in range(right, left - 1, -1):
                    result.append(matrix[bottom][j])
                bottom -= 1
            
            # 向上遍历（需要检查是否还有列）
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1
        
        return result

public class Solution {
    public IList<int> SpiralOrder(int[][] matrix) {
        var result = new List<int>();
        if (matrix.Length == 0 || matrix[0].Length == 0) return result;
        
        int m = matrix.Length, n = matrix[0].Length;
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        
        while (top <= bottom && left <= right) {
            // 向右遍历
            for (int j = left; j <= right; j++) {
                result.Add(matrix[top][j]);
            }
            top++;
            
            // 向下遍历
            for (int i = top; i <= bottom; i++) {
                result.Add(matrix[i][right]);
            }
            right--;
            
            // 向左遍历（需要检查是否还有行）
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    result.Add(matrix[bottom][j]);
                }
                bottom--;
            }
            
            // 向上遍历（需要检查是否还有列）
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.Add(matrix[i][left]);
                }
                left++;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    const result = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        for (let col = left; col <= right; col++) {
            result.push(matrix[top][col]);
        }
        top++;
        
        for (let row = top; row <= bottom; row++) {
            result.push(matrix[row][right]);
        }
        right--;
        
        if (top <= bottom) {
            for (let col = right; col >= left; col--) {
                result.push(matrix[bottom][col]);
            }
            bottom--;
        }
        
        if (left <= right) {
            for (let row = bottom; row >= top; row--) {
                result.push(matrix[row][left]);
            }
            left++;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历矩阵中的每个元素一次
空间复杂度O(1)只使用了常数级别的额外空间（不计输出数组）

相关题目