# 54. Spiral Matrix

## 1.問題&#x20;

* 給予一個m \* n的矩陣, 回傳一個由旋轉順序構成的list

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LN__HFQDfXcoazCKNt7%2F-LN_aKXugmOPrANw9GqI%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-29%20%E4%B8%8B%E5%8D%889.51.19.png?alt=media\&token=c7549803-9453-4905-8870-024d24bce396)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
* parameter
  * 2D list
* test input
* 說明想法
  * 用上, 下, 左, 右四個指標來移動, 當left <= right -1且up <= down - 1時繼續執行以下動作
    * 上排: 從left到right, 依序將數值放到res, 並遞增up
    * 右排: 從up到down, 依序將數值放到res, 並遞減right
    * 下排: 從right到left, 依序將數值放到res, 並遞減down
    * 左排: 從down到up, 依序將數值放到res, 並遞增left
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty()) {
            return res;
        }
        int m = matrix.size();
        int n = matrix[0].size();
        int index = 0, up = 0, right = n, left = 0, down = m;
        
        while (left <= right- 1 && up <= down - 1) {
            for (int i = left; i < right; i++) {
                if (res.size() < m * n) {
                    res.push_back(matrix[up][i]);
                }
            }
            up++;
            
            for (int i = up; i < down; i++) {
                if (res.size() < m * n) {
                    res.push_back(matrix[i][right - 1]);
                }
            }
            right--;
            
            for (int i = right - 1; i >= left; i--) {
                if (res.size() < m * n) {
                    res.push_back(matrix[down - 1][i]);
                }
            }
            down--;
            
            for (int i = down - 1; i >= up; i--) {
                if (res.size() < m * n) {
                    res.push_back(matrix[i][left]);
                }
            }
            left++;
        }
        
        return res;
    }
};
```
