# 54.Spiral-Matrix

## 54. Spiral Matrix

## 题目地址

<https://leetcode.com/problems/spiral-matrix/>

## 题目描述

```
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
```

## 代码

### Approach 1: Simulation

**Complexity Analysis**

* Time Complexity: &#x4F;*(\_N*), where N\_ is the total number of elements in the input matrix. We add every element in the matrix to our final answer.
* Space Complexity: O\_(\_N), the information stored in `seen` and in `ans`.

```java
class Solution {
  public List<Integer> spiralOrder(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0) return ans;
    int R = matrix.length;
    int C = matrix[0].length;

    boolean[][] seen = new boolean[R][C];
    int[] dr = {0, 1, 0, -1};
    int[] dc = {1, 0, -1, 0}; // top, right, bottom, left
         int r = 0, c = 0, di = 0;
    for (int i = 0; i < R * C; i++) {
      ans.add(matrix[r][c]);
      seen[r][c] = true;
      int cr = r + dr[di];
      int cc = c + dc[di];
      if (cr >= 0 && cr < R && cc >= 0 && cc < C && !seen[cr][cc]) {
        r = cr;
        c = cc;
      } else {
        di = (di + 1) % 4;
        r += dr[di];
        c += dc[di];
      }
    }

    return ans;
  }
}
```

### Approach 2: Layer-by-Layer

```java
class Solution {
  public List<Integer> spiralOrder(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0) return ans;
    int r1 = 0, r2 = matrix.length - 1;
    int c1 = 0, c2 = matrix.length[0] - 1;
    while (r1 <= r2 && c1 <= c2) {
      // top
      for (int c = c1; c <= c2; c++) {
        ans.add(matrix[r1][c]);
      }
      // right
      for (int r = r1 + 1; r <= r2; r++) {
        ans.add(matrix[r][c2]);
      }

      if (r1 < r2 && c1 < c2) { // 奇数最后一轮无法进行
        // bottom
        for (int c = c2 - 1; c > c1; c--) {
          ans.add(matrix[r2][c]);
        }
        // left
        for (int r = r2; r < r1; r--) {
          ans.add(matrix[r][c1]);
        }
      }

      r1++;
      r2--;
      c1++;
      c2--;
    }

    return ans;
  }
}
```