问题描述 小蓝有一个序列 a[1], a[2], ..., a[n]。 给定一个正整数 k，请问对于每一个 1 到 n 之间的序号 i，a[i-k], a[i-k+1], ..., a[i+k] 这 2k+1 个数中的最小值是多少？当某个下标超过 1 到 n 的范围时，数不存在，求最小值时只取存在的那些值。 输入格式 输入的第一行包含一整数 n。 第二行包含 n 个整数，分别表示 a[1], a[2], ..., a[n]。 第三行包含一个整数 k 。 输出格式 输出一行，包含 n 个整数，分别表示对于每个序号求得的最小值。 样例输入 5 5 2 7 4 3 1 样例输出 2 2 2 3 3 请用Python代码实现

n = int(input())
a = list(map(int, input().split()))
k = int(input())

# 初始化双端队列
q = []
for i in range(k):
    while q and a[i] <= a[q[-1]]:
        q.pop()
    q.append(i)

# 处理剩余元素
res = [a[q[0]]]
for i in range(k, n):
    # 判断队首元素是否在窗口内
    if q and q[0] <= i - k:
        q.pop(0)
    # 维护单调性
    while q and a[i] <= a[q[-1]]:
        q.pop()
    q.append(i)
    res.append(a[q[0]])

print(*res)

相关问题

小蓝有一个序列a[1], a[2]. .... a[n]. 给定一个正整数k，请问对于每一个1到n之间的序号i，a[i-k], a[i-k+1].... a[i+k]这2k+1个数中的最小值是多少?当某个下标超过1到n的范围时，数不存在，求最小值时只取存在的那些值

对于每一个1到n之间的序号i，a[i-k], a[i-k+1].... a[i+k]这2k+1个数中的最小值是a[max(i-k,1)], a[max(i-k+1,1)].... a[min(i+k,n)]中的最小值。