螺旋矩阵

## 1 题目

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

**示例 1：**

![](/media/202107/2021-07-01_193627.png)

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

**示例 2：**

![](/media/202107/2021-07-01_193635.png)

```txt
输入：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

## 2 问题分析

1. 解决这个问题的基本思路是将整个矩阵划分为**四个区域**，然后**分区域**来进行**输出**，为了减少考虑的情况，拟将矩阵划分为如下图所示的区域：

![](/media/202206/2022-06-02_111817_004461.png)
2. 从上面划分的区域中我们可以看出，**上下**和**左右**对应的区域分别是**对称**的，因此只要将其中两个区域写好之后，另外两个区域就是其相反的输出，假设需要进行的圈数为$round$，矩阵的宽为$m$，长为$n$，则：

1. 上区域输出的代码为：

```java
      for (int j = i; j <= n - i - 1; j++) {res.add(matrix[i][j]);}
      ```

因此对应的下区域输出的代码为：

```java
      for (int j = n - i - 1; j >= i; j--) {res.add(matrix[m - i - 1][j]);}
      ```
   2. 左区域输出的代码为：

```java
      for (int j = m - i - 2; j > i; j--) {res.add(matrix[j][i]);}
      ```

因此对应的右区域输出的代码为：

```java
      for (int j = i + 1; j <= m - i - 2; j++) {res.add(matrix[j][n - i - 1]);}
      ```
3. 但同时我们还需要考虑两种特殊情况，这两种特殊情况可能会造成**元素的重复输出**：

1. **纵轴单独**：

![](/media/202206/2022-06-02_112556_511419.png)

这种情况其实我们只要**将这个单独的纵轴放在右侧区域**即可（因为按照**顺时针旋转**，**右侧区域相比于左侧区域先进行遍历**），也就是**让左侧遍历的纵轴小于右侧**即可，即 `i < n - i - 1`，其中当前遍历的元素坐标为 `matrix[j][i]`。
   2. **横轴单独**：

![](/media/202206/2022-06-02_113115_724284.png)

这种情况与纵轴单独类似，只要**将单独的横轴放在上侧区域**即可（因为按照**顺时针旋转**，**上侧区域相比于下侧区域先进行遍历**），也就是**让下侧遍历的横轴大于上侧**即可，即 `i < m - i - 1`，其中当前遍历的元素坐标为 `matrix[m - i - 1][j]`。
4. 因此区域完整的输出代码为：

```java
   for (int i = 0; i < round; i++) {
       //  上
       for (int j = i; j <= n - i - 1; j++) {res.add(matrix[i][j]);}
       //  右
       for (int j = i + 1; j <= m - i - 2; j++) {res.add(matrix[j][n - i - 1]);}
       //  下
       for (int j = n - i - 1; j >= i && i < m - i - 1; j--) {res.add(matrix[m - i - 1][j]);}
       //  左
       for (int j = m - i - 2; j > i && i < n - i - 1; j--) {res.add(matrix[j][i]);}
   }
   ```
5. 还有一个关键的问题是需要进行的圈数$round$如何确定，通过观测我们可以发现**需要进行的圈数和矩阵的长度和宽度的最小值有关**，假设$min = Math.min(m, n)$，则：

```java
   round = (min % 2 == 0) ? min / 2 : min / 2 + 1;
   ```

## 3 参考代码

```java
/**
 * 54. 螺旋矩阵
 * @param matrix    矩阵
 * @return  按照顺时针螺旋顺序，返回矩阵中的所有元素
 */
public List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length, min = Math.min(m, n);
    int round = (min % 2 == 0) ? min / 2 : min / 2 + 1;
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < round; i++) {
        //  上
        for (int j = i; j <= n - i - 1; j++) {res.add(matrix[i][j]);}
        //  右
        for (int j = i + 1; j <= m - i - 2; j++) {res.add(matrix[j][n - i - 1]);}
        //  下
        for (int j = n - i - 1; j >= i && i < m - i - 1; j--) {res.add(matrix[m - i - 1][j]);}
        //  左
        for (int j = m - i - 2; j > i && i < n - i - 1; j--) {res.add(matrix[j][i]);}
    }
    return res;
}
```

## 4 参考文献

1. [54. 螺旋矩阵](https://leetcode-cn.com/problems/spiral-matrix)。