练63.1 蛇行三角形

解题思路

按i+j的对角线填数。第s条线从(s,0)向右上移动，即依次(s,0),(s-1,1)…(0,s)，数字连续递增。最后按行输出。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

只填i+j<n的三角区域；每行长度n-i。

复杂度

时间O(n²)，空间O(n²)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    int v = 1;
    for (int s = 0; s < n; s++)
        for (int i = s; i >= 0; i--)
            a[i][s - i] = v++;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            if (j)
                cout << " ";
            cout << a[i][j];
        }
        cout << "\n";
    }
    return 0;
}