54. 螺旋矩阵

---

题目：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]

解题思路

为什么选择这个方法

1. 顺时针遍历的特点： 我们可以通过维护四个边界（上、下、左、右），实现螺旋顺序的遍历。当我们遍历完一行或者一列之后，就需要将边界缩小，进入到下一个“圈层”的遍历。每次移动边界，我们都确保按照顺时针的顺序访问矩阵的每个元素。

2. 为什么不用递归： 虽然递归看起来是个不错的选择，但递归会涉及额外的函数调用栈和复杂的边界管理，这可能会导致不必要的性能开销。在这种题目中，使用迭代的方式不仅直观，而且更易于理解和调试。

3. 为什么要四个边界？ 四个边界分别代表了矩阵中的四个边缘，它们帮助我们在遍历过程中控制边界范围，逐步缩小遍历的区域。通过边界的逐步收缩，我们可以实现“螺旋”状的遍历，直到所有元素被访问完。

具体步骤

1. 初始化四个边界：

   • top：最上面一行的索引。
   • bottom：最下面一行的索引。
   • left：最左边一列的索引。
   • right：最右边一列的索引。

2. 开始遍历： 我们使用一个循环，不断收缩四个边界，直到top > bottom或者left > right。每次遍历时，都会按照顺时针的顺序，访问矩阵的元素：

   • 从左到右遍历上边界（top），然后将上边界top向下移动。
   • 从上到下遍历右边界（right），然后将右边界right向左移动。
   • 从右到左遍历下边界（bottom），然后将下边界bottom向上移动。
   • 从下到上遍历左边界（left），然后将左边界left向右移动。

3. 重复遍历，直到所有元素都被访问： 每次遍历时，我们都会将元素加入结果列表。每完成一圈遍历后，收缩边界，进入下一个更内层的矩阵区域，直到所有的元素都被遍历。

为什么这样做而不是其他方法？

• 方法一：递归： 递归方式的实现也是可行的，但递归带来的是额外的函数调用开销，同时需要多层函数的状态管理，对初学者来说理解起来可能较为复杂。而且在处理较大的矩阵时，递归方法可能会导致栈溢出。

• 方法二：使用堆栈： 虽然我们也可以将矩阵元素按顺时针方向放入堆栈，然后再从堆栈中逐一弹出，但这种方法不如直接遍历的方式直观，而且代码会更加复杂。没有必要使用堆栈来额外存储结果。

• 方法三：二维数组直接遍历： 直接遍历矩阵时，我们无法控制顺时针的顺序，必须手动管理遍历的方向。而四个边界的方案提供了非常简洁的方式来按顺时针顺序逐步遍历所有元素。它能保证我们每一步都清晰明确地知道当前访问哪个方向的元素。

最优解：迭代顺时针遍历

代码实现

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read matrix dimensions
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // Read matrix elements
        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();
            }
        }

        Solution solution = new Solution();
        List<Integer> result = solution.spiralOrder(matrix);

        // Print the result
        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;  // 处理空矩阵的边界条件
        }

        int top = 0;     // 上边界
        int bottom = matrix.length - 1;  // 下边界
        int left = 0;    // 左边界
        int right = matrix[0].length - 1;  // 右边界

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

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

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

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

        return result;
    }
}

---

时间复杂度分析

1. 遍历矩阵：
   • 每个元素都被精确访问一次，没有重复访问。
   • 访问顺序：从外到内按顺时针方向螺旋遍历。

总时间复杂度：O(m × n)，其中 m 是矩阵的行数，n 是矩阵的列数。

---

空间复杂度分析

1. 结果存储：
   • 需要一个 List 存储所有矩阵元素，大小为 m × n。
2. 辅助变量：
   • 仅使用了四个边界变量（top、bottom、left、right），占用常数空间。

总空间复杂度：O(m × n)，主要由结果列表决定。

---