HJ35. 蛇形矩阵
题目描述
输出一个 n 行 n 列的上三角蛇形矩阵。构造方法：从 1 开始填充自然数，第 1 行第 1 列元素为 1，不断沿"右上"方向斜向填充，直到填满上三角 n(n+1)/2 个格子。
输入格式
- 一行一个整数 n。
输出格式
- n 行，第 i 行输出 n-i+1 个数（上三角），行内空格分隔。
示例
示例 1
输入：
4
输出：
1 3 6 10
2 5 9
4 8
7
解题思路
第一步：理解问题本质
上三角矩阵共 n(n+1)/2 个格子，按"副对角线"（row+col 相同）斜向填充自然数。第 d 条副对角线包含 d+1 个格子。
第二步：暴力解法（按坐标推公式）
推导每个位置与行、列的数学公式逐个计算。
问题：公式推导复杂且容易出错，边界难以处理。
第三步：优化解法（按副对角线逐条填充）
利用"副对角线上 row+col=d"这一性质，从 d=0 到 n-1 逐条填充。每条副对角线从行号大到小（row 从 d 到 0），col = d - row，依次填自然数。
num = 1
for d in range(n):
for row in range(d, -1, -1):
col = d - row
mat[row][col] = num
num += 1
第四步：最优解法（模拟 + 上三角输出）
填充完后，按行输出上三角：第 row 行输出 col 从 0 到 n-1-row 的格子。
out = []
for row in range(n):
out.append(' '.join(str(mat[row][col]) for col in range(n - row)))
print('\n'.join(out))
完整代码实现
算法可视化 · 逐帧回放这道题的代码76 帧 · 录制输入
import sys
def solve() -> None:
"""主求解函数"""
n = int(sys.stdin.readline().strip())
mat = [[0] * n for _ in range(n)]
num = 1
# 按副对角线（row+col=d）逐条填充
for d in range(n):
for row in range(d, -1, -1):
col = d - row
mat[row][col] = num
num += 1
# 输出上三角：第 row 行输出 col 0..n-1-row
out = []
for row in range(n):
out.append(' '.join(str(mat[row][col]) for col in range(n - row)))
print('\n'.join(out))
if __name__ == "__main__":
solve()
示例推演
以 n=4 为例，按副对角线填充：
d=0（row+col=0）：row 从 0 到 0，col=0 → mat[0][0]=1
d=1（row+col=1）：row 从 1 到 0
- row=1, col=0 →
mat[1][0]=2 - row=0, col=1 →
mat[0][1]=3d=2（row+col=2）：row 从 2 到 0 - row=2, col=0 →
mat[2][0]=4 - row=1, col=1 →
mat[1][1]=5 - row=0, col=2 →
mat[0][2]=6d=3（row+col=3）：row 从 3 到 0 - row=3, col=0 →
mat[3][0]=7 - row=2, col=1 →
mat[2][1]=8 - row=1, col=2 →
mat[1][2]=9 - row=0, col=3 →
mat[0][3]=10
填充后的上三角矩阵：
| 行 | 列0 | 列1 | 列2 | 列3 |
|---|---|---|---|---|
| 0 | 1 | 3 | 6 | 10 |
| 1 | 2 | 5 | 9 | |
| 2 | 4 | 8 | ||
| 3 | 7 |
输出上三角：
1 3 6 10
2 5 9
4 8
7
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 坐标公式推导 | O(n²) | O(n²) | 公式复杂易错 |
| 副对角线模拟 | O(n²) | O(n²) | 按副对角线逐条填充 |
上三角格子总数 n(n+1)/2
易错点总结
1. 副对角线顺序
每条副对角线从行号大到小填充（row 从 d 到 0），这样才能得到"右上"方向的斜向递增序列。
2. col 的计算
col = d - row，由副对角线 row+col=d 直接得出，不要单独推导。
3. 上三角输出范围
第 row 行只输出 col 从 0 到 n-1-row，即 n-row 个数，不要多输出。
4. 行内空格分隔
每行数字之间用空格分隔，行末无多余空格。
扩展思考
- 本题本质是"按副对角线填充"，可推广到其它矩阵填充模式（螺旋矩阵、回形矩阵等）。
- 输出时用列表收集再
join是避免行尾多余空格的常用技巧。