我的LeetCode代碼倉：https://github.com/617076674/LeetCode
原題連結：https://leetcode-cn.com/problems/spiral-matrix/description/
題目描述：
知識點：數組
思路一：用一個m行n列的數組visited記錄該位置元素是否已被通路過
對于一個m行n列的數組matrix，我們要螺旋周遊之，我們需要螺旋多少圈呢？
我們可以通過找規律得出上述問題的答案。
| m | n | turn |
| 3 | 4 | 2 |
| 3 | 5 | 2 |
| 3 | 9 | 2 |
| 9 | 3 | 2 |
| 9 | 5 | 3 |
設min為m和n中的較小值，如果min能被2整除，那麼我們需要螺旋min / 2圈。如果min不能被2整除，那麼我們需要螺旋min / 2 + 1圈。
對于每一圈螺旋，我們都在上右下左4條邊上依次周遊沒有被通路過的位置，并将周遊到的沒有被通路過的位置标記成已經被通路過。
時間複雜度和空間複雜度均是O(m * n)。
JAVA代碼：
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
int m = matrix.length;
if(m == 0) {
return list;
}
int n = matrix[0].length;
if(n == 0) {
return list;
}
boolean[][] visited = new boolean[m][n];
int turn = Math.min(m, n) % 2 == 0 ? Math.min(m, n) / 2 : Math.min(m, n) / 2 + 1;
for (int k = 0; k < turn; k++) {
for (int i = 0; i < n; i++) {
if(!visited[k][i]) {
list.add(matrix[k][i]);
visited[k][i] = true;
}
}
for (int i = 0; i < m; i++) {
if(!visited[i][n - 1 - k]) {
list.add(matrix[i][n - 1 - k]);
visited[i][n - 1 - k] = true;
}
}
for (int i = n - 1; i >= 0; i--) {
if(!visited[m - 1 - k][i]) {
list.add(matrix[m - 1 - k][i]);
visited[m - 1 - k][i] = true;
}
}
for (int i = m - 1; i >= 0; i--) {
if(!visited[i][k]) {
list.add(matrix[i][k]);
visited[i][k] = true;
}
}
}
return list;
}
}
LeetCode解題報告：
思路二：實時更新螺旋的四個邊界left、right、top、bottom的值
一開始，我們的四個邊界分别如下：left = 0，right = n - 1，top = 0，bottom = m - 1。在while循環中，我們每周遊一條邊就相應地改變某一邊界的值，令其自增1或者自減1。
需要注意的是，在周遊下邊界和左邊界時，由于此時top值和right值均發現了改變，對于周遊下邊界時，需要重新判斷bottom是否大于等于top，對于周遊左邊界時，需要重新判斷right是否大于等于left。
時間複雜度是O(m * n)。空間複雜度是O(1)。
JAVA代碼：
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
int m = matrix.length;
if(m == 0) {
return list;
}
int n = matrix[0].length;
if(n == 0) {
return list;
}
int top = 0;
int bottom = m - 1;
int left = 0;
int right = n - 1;
while(top <= bottom && left <= right) {
for (int i = left; i <= right; i++) {
list.add(matrix[top][i]);
}
top++;
for (int i = top; i <= bottom; i++) {
list.add(matrix[i][right]);
}
right--;
if(bottom >= top) {
for (int i = right; i >= left; i--) {
list.add(matrix[bottom][i]);
}
bottom--;
}
if(right >= left) {
for (int i = bottom; i >= top; i--) {
list.add(matrix[i][left]);
}
left++;
}
}
return list;
}
}
LeetCode解題報告：