概要

長さ \(K\) の連続区間ごとに「最大値−最小値」を計算し、その最大を求めます。各区間の最大・最小を高速に更新するのがポイントです。

考察

各 \(K\) 日間の変動幅は、その区間の最高気温 \(\max\) と最低気温 \(\min\) を使って \( \max - \min\) と表せます。したがって問題は「全ての長さ \(K\) の区間について、\(\max\) と \(\min\) を求め、差の最大を取る」ことです。

素朴にやると、各区間 \([l, l+K-1]\) について - 最大値を求めるのに \(O(K)\) - 最小値を求めるのに \(O(K)\)
かかり、区間数が \(N-K+1\) 個あるので合計 \(O(NK)\) になります。
\(N \le 2\times 10^5\) で \(K\) も同程度になり得るため、これは間に合いません。

そこで「スライドする窓（区間）」に対して、最大値・最小値を毎回作り直すのではなく、1 日進めたときに情報を更新して \(O(1)\)（償却）で取り出せるようにします。

アルゴリズム

単調キュー（Monotonic Queue）を 2 本使います。

• 最大値用 deque maxdq：気温が 前から後ろへ単調減少 になるように、添字を保持する

  • 新しい値 \(x=H_i\) を入れるとき、末尾から見て \(H[\text{末尾}] \le x\) の要素は将来最大になれないので削除し、\(i\) を追加します。
  • 先頭は常に「現在の窓内の最大値の添字」になります。

• 最小値用 deque mindq：気温が 前から後ろへ単調増加 になるように、添字を保持する

  • 新しい値 \(x\) を入れるとき、末尾から見て \(H[\text{末尾}] \ge x\) の要素は将来最小になれないので削除し、\(i\) を追加します。
  • 先頭は常に「現在の窓内の最小値の添字」になります。

窓の左端を \(left = i-K+1\) とすると、\(left \ge 0\) の時点で長さ \(K\) の区間が完成しています。このとき - 先頭の添字が窓の外（\(< left\)）なら、先頭から取り除く（popleft） - 最大値は H[maxdq[0]] - 最小値は H[mindq[0]] - 差 diff = H[maxdq[0]] - H[mindq[0]] で答えを更新

具体例

\(H=[3,1,4,1,5],\ K=3\) を考えると、区間は - \([3,1,4]\)：\(\max=4,\min=1,\ diff=3\) - \([1,4,1]\)：\(\max=4,\min=1,\ diff=3\) - \([4,1,5]\)：\(\max=5,\min=1,\ diff=4\)
最大は 4。単調キューを使うと、この各区間の \(\max,\min\) を毎回走査せずに取り出せます。

計算量

• 時間計算量: \(O(N)\)
  各要素は deque に高々 1 回入って高々 1 回出るため、全体で線形です（償却 \(O(1)\)）。
• 空間計算量: \(O(K)\)（最大でも \(O(N)\)）
  deque に保持されるのは窓付近の添字で、各 deque の長さは高々 \(K\) 程度です。

実装のポイント

• deque には 値ではなく添字を入れると、窓から外れたかどうか（\(< left\)）を簡単に判定できます。

• 最大用は「末尾の値 \(\le\) 新値なら削除」、最小用は「末尾の値 \(\ge\) 新値なら削除」と、比較向きが逆になります。

• 窓が完成するのは \(i \ge K-1\)（つまり \(left \ge 0\)）のときだけなので、そのタイミングで差を計算します。

• 気温は負にもなり得ますが、差 \(\max-\min\) は必ず \(0\) 以上なので、初期値 ans = 0 で問題ありません。

  ソースコード

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    H = data[2:2+N]

    maxdq = deque()  # indices, H values decreasing
    mindq = deque()  # indices, H values increasing

    ans = 0
    for i, x in enumerate(H):
        while maxdq and H[maxdq[-1]] <= x:
            maxdq.pop()
        maxdq.append(i)

        while mindq and H[mindq[-1]] >= x:
            mindq.pop()
        mindq.append(i)

        left = i - K + 1
        if left >= 0:
            while maxdq[0] < left:
                maxdq.popleft()
            while mindq[0] < left:
                mindq.popleft()
            diff = H[maxdq[0]] - H[mindq[0]]
            if diff > ans:
                ans = diff

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。