# 59. Spiral Matrix II

## 1.問題 

* 給予一個正整數n, 產生一個正方形矩形, 以螺旋方式存放1 \~ n^2

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNbfaAKz0WhJWb-rltV%2F-LNbrGgEMWQFx60Gv2Uv%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-30%20%E4%B8%8A%E5%8D%888.24.35.png?alt=media\&token=0b2f3ca4-c5ef-40ec-8129-2a30c5e54d46)

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

* 提問
* parameter
  * 整數n
  * 回傳一個2D list
* test input
* 說明想法
  * Create一個2D list, 並且填入對應的數字
  * 為了怕overflow, 填入數字時可以計算cnt
  * 用上, 下, 左, 右四個指標來移動, 當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<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        if (n == 0) {
            return res;
        }
        int top = 0, bottom = n, left = 0, right = n, cnt = 0, total = n * n;
        while (top <= bottom - 1 && left <= right - 1) {
            for (int i = left; i < right; i++) {
                if (cnt < total) {
                    res[top][i] = cnt + 1; 
                    cnt++;
                }
            }
            ++top;
            
            for (int i = top; i < bottom; i++) {
                if (cnt < total) {
                    res[i][right - 1] = cnt + 1; 
                    cnt++;
                }
            }
            --right;
            
            for (int i = right - 1; i >= left; i--) {
                if (cnt < total) {
                    res[bottom - 1][i] = cnt + 1; 
                    cnt++;
                }
            }
            --bottom;
            
            for (int i = bottom - 1; i >= top; i--) {
                if (cnt < total) {
                    res[i][left] = cnt + 1; 
                    cnt++;
                }
            }
            ++left;
        }
        
        return res;
    }
};
```