题目的主要信息：

蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形
形如：

1 3 6 10 15

2 5 9 14

4 8 13

7 12

11

方法一：顺序填表

具体做法：

我们可以准备一个 $n * n$ 的二维矩阵，只填充矩阵上半个三角形，而填充顺序从每行的第一列开始，每次都往右上角方向填充元素，即矩阵行坐标递减，列坐标递增，而填充的数字依次增加就行了。 alt

然后我们顺序遍历这个矩阵，将非零的元素依次输出即可。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n; 
    while(cin >> n){
        vector<vector<int> > matrix(n, vector<int>(n, 0)); //定义一个n*n的矩阵
        int num = 1;
        for(int i = 0; i < n; i++){
            int j = i, k = 0;
            while(j >= 0){
                matrix[j][k] = num; //录入数字
                num++;
                j--; //往右上方移
                k++;
            }
        }
        for(int i = 0; i < n; i++){ //遍历数组每一行
            int j = 0;
            while(matrix[i][j] != 0 && j < n){ //每行只输出前面非零部分
                cout << matrix[i][j] << " ";
                j++;
            }
            cout << endl; //换行
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ，填充和输出矩阵都遍历 $n (n + 1) / 2$ 个矩阵空间
空间复杂度： $O (n^{2})$ ，使用二维矩阵作为辅助数组

方法二：数学规律

具体做法：

仔细观察这样的蛇形矩阵，我们可以尝试找规律：

对于每一行第一个元素，我们发现2与1之间相差为1，4与2之间相差为2，7与4之间相差为3，11与7之间相差为4，则第 $i$ 行的第一个元素与它的下一行是相差了个行号（从1开始）。

对于每一行的每个元素，我们发现3与1之间相差为2，6与3之间相差为3，10与6之间相差为4，15与10之间相差为5，则第 $j$ 列与它的前一列相差为其列号（从1开始）。

alt

有了这个规律，我们遍历这样的上三角形，对每个位置累加出数字即可。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n; 
    while(cin >> n){
        int k = 1; //起始元素为1
        for(int i = 1; i <= n; i++){ //遍历每一行
            cout << k << " ";  //输出每行首
            int temp = k;
            for(int j = i + 1; j <= n; j++){ //遍历本行的数
                temp += j; //每个数相差为j
                cout << temp << " ";
            }
            cout << endl;
            k += i; //下一行的首为这行首加上这行行号
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ，还是要遍历 $n (n + 1) / 2$ 个元素
空间复杂度： $O (1)$ ，无额外空间

题解 | #蛇形矩阵#

题目的主要信息：

方法一：顺序填表

方法二：数学规律