分数: 300 分
问题陈述
高桥在气象台工作,记录日平均气温。温度记录为简化的整数值,范围为 1 to 9 (9 级)。
有一天,高桥决定分析连续的温度数据 N过去的天。高桥重点关注连续的总温度 K天窗口,并且想要计算每个连续的总数 K天窗口,然后求其中最大值和最小值的差值。差异越大,说明该时期气温波动越剧烈。
具体来说,考虑到温度记录 N 天为 A_1, A_2, \dots, A_N,有 N - K + 1 连续的总值 K天窗。也就是说,对于 i = 1, 2, \dots, N - K + 1,我们计算:
S_i = \sum_{j=0}^{K-1} A_{i+j}
找出最大值和最小值之间的差异 S_1, S_2, \dots, S_{N-K+1}.
约束
- 1 \leq K \leq N \leq 10^5
- 1 \leq A_i \leq 9
- 所有输入值均为整数。
输入
N K A_1 A_2 \dots A_N
- 第一行包含一个整数 N 表示观察天数和一个整数 K 代表感兴趣的连续天数,以空格分隔。
- 第二行包含整数 A_1, A_2, \dots, A_N 代表每天的温度,以空格分隔。
输出
打印最大值和最小值之间的差值 S_1, S_2, \dots, S_{N-K+1} 在一行上。
示例输入 1
5 3 2 5 3 1 4
示例输出 1
2
示例输入 2
10 4 3 1 4 1 5 9 2 6 5 3
示例输出 2
13
示例输入 3
20 5 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9
示例输出 3
8