蓝桥杯-MAX最值差


import os
import sys

# 请在此输入您的代码
from collections import deque

max_q = deque()
min_q = deque()

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = float('-inf')

for i in range(n):
    left = i - k if i >= k else 0

    # 超出范围的移除
    while max_q and max_q[0] < left:
        max_q.popleft()
    # 维护队列
    while max_q and a[max_q[-1]] < a[i]:
        max_q.pop()
    max_q.append(i)

    while min_q and min_q[0] < left:
        min_q.popleft()
    while min_q and a[min_q[-1]] > a[i]:
        min_q.pop()
    min_q.append(i)

    ans = max(ans, a[max_q[0]] - a[min_q[0]])
print(ans)