螺旋矩阵遍历

题解思路

这道题的核心是模拟螺旋遍历矩阵的过程。遍历方式如下：

1. 从左到右遍历上边界
2. 从上到下遍历右边界
3. 从右到左遍历下边界（如果仍然存在）
4. 从下到上遍历左边界（如果仍然存在）

然后不断缩小边界范围，直到遍历完整个矩阵。

算法设计

我们可以定义四个变量来表示边界：

• top 表示上边界
• bottom 表示下边界
• left 表示左边界
• right 表示右边界

遍历过程中按照顺时针方向进行：

1. 遍历 top 行，从 left 到 right，然后 top++
2. 遍历 right 列，从 top 到 bottom，然后 right--
3. 如果仍然有 bottom 行，则从 right 到 left 遍历该行，bottom--
4. 如果仍然有 left 列，则从 bottom 到 top 遍历该列，left++

不断重复上述过程，直到所有元素都被访问。

复杂度分析

由于我们遍历矩阵的每个元素一次，时间复杂度为 O(m * n)，其中 m 为行数，n 为列数。
额外使用了一个结果数组，空间复杂度为 O(1)（如果不考虑输出存储）。

代码实现

Python 代码

class Solution:
    def spiralOrder(self, matrix):
        if not matrix or not matrix[0]:
            return []

        m, n = len(matrix), len(matrix[0])
        result = []
        
        # 定义边界
        top, bottom = 0, m - 1
        left, right = 0, n - 1

        while top <= bottom and left <= right:
            # 从左到右
            for i in range(left, right + 1):
                result.append(matrix[top][i])
            top += 1  # 上边界下移
            
            # 从上到下
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1  # 右边界左移

            # 从右到左
            if top <= bottom:
                for i in range(right, left - 1, -1):
                    result.append(matrix[bottom][i])
                bottom -= 1  # 下边界上移

            # 从下到上
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1  # 左边界右移
        
        return result

# 读取输入
if __name__ == "__main__":
    m, n = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(m)]
    solution = Solution()
    print(" ".join(map(str, solution.spiralOrder(matrix))))

Java 代码

import java.util.*;

public class Main {
    public class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> result = new ArrayList<>();
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return result;
            }
            
            int m = matrix.length, n = matrix[0].length;
            int top = 0, bottom = m - 1;
            int left = 0, right = n - 1;

            while (top <= bottom && left <= right) {
                // 从左到右
                for (int i = left; i <= right; i++) {
                    result.add(matrix[top][i]);
                }
                top++; // 上边界下移

                // 从上到下
                for (int i = top; i <= bottom; i++) {
                    result.add(matrix[i][right]);
                }
                right--; // 右边界左移

                // 从右到左
                if (top <= bottom) {
                    for (int i = right; i >= left; i--) {
                        result.add(matrix[bottom][i]);
                    }
                    bottom--; // 下边界上移
                }

                // 从下到上
                if (left <= right) {
                    for (int i = bottom; i >= top; i--) {
                        result.add(matrix[i][left]);
                    }
                    left++; // 左边界右移
                }
            }
            return result;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] matrix = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        
        Main main = new Main();
        Solution solution = main.new Solution();
        List<Integer> result = solution.spiralOrder(matrix);
        
        for (int i = 0; i < result.size(); i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(result.get(i));
        }
    }
}

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

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;
        int left = 0, right = n - 1;

        while (top <= bottom && left <= right) {
            // 从左到右
            for (int i = left; i <= right; i++) {
                result.push_back(matrix[top][i]);
            }
            top++; // 上边界下移

            // 从上到下
            for (int i = top; i <= bottom; i++) {
                result.push_back(matrix[i][right]);
            }
            right--; // 右边界左移

            // 从右到左
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.push_back(matrix[bottom][i]);
                }
                bottom--; // 下边界上移
            }

            // 从下到上
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.push_back(matrix[i][left]);
                }
                left++; // 左边界右移
            }
        }
        return result;
    }
};

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> matrix(m, vector<int>(n));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    Solution solution;
    vector<int> result = solution.spiralOrder(matrix);

    for (size_t i = 0; i < result.size(); i++) {
        if (i > 0) cout << " ";
        cout << result[i];
    }
    cout << endl;

    return 0;
}

Leetcode 19.螺旋矩阵-原题链接

题目内容

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

输入描述

第一行两个整数$m，n$ 接下来$m$行，每行$n$列，代表矩阵$matrix$。 每行的数字之间以空格分隔。

输出描述

输出一行，按题目要求顺序输出每个数字，数字之间以空格分隔。

样例1

输入

3 3
1 2 3
4 5 6
7 8 9

输出

1 2 3 6 9 8 7 4 5

样例2

输入

3 4
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.lengt$
• $n == matrix[i].length$
• $1 <= m, n <= 10$
• $-100 <= matrix[i][j] <= 100$