概要

\(N\) 日間の気温データから、連続する \(K\) 日間を選んだときの「最高気温と最低気温の差」の最大値を求める問題です。

考察

この問題の肝は、「長さ \(K\) のスライディングウィンドウ内での最大値と最小値をいかに効率よく求めるか」という点にあります。

素朴なアプローチ

各 \(i\) 日目から始まる \(K\) 日間について、毎回最大値と最小値を計算するとどうなるでしょうか。 - ウィンドウの開始位置： \(N - K + 1\) 通り - 各ウィンドウ内の最大・最小探索： \(O(K)\)

全体の計算量は \(O(N \times K)\) となります。制約を見ると \(N, K \leq 2 \times 10^5\) であるため、最悪の場合 \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2 秒程度）に間に合いません（TLE）。

効率的なアプローチ

ウィンドウを 1 日ずつずらす際、ほとんどの要素は共通しています。この性質を利用して、最大値と最小値を高速に更新する手法が必要です。これを実現するのが「スライディングウィンドウ最小値（最大値）」と呼ばれるアルゴリズムで、デック（deque: 両端キュー）を用いることで各ウィンドウの値を効率的に管理できます。

アルゴリズム

デックを用いて、ウィンドウ内の「最大値の候補」と「最小値の候補」を常に保持します。最大値を管理するデックを例に説明します。

1. 要素の追加: 新しい日の気温 \(H_i\) を追加する際、デックの末尾にある「 \(H_i\) 以下の値」をすべて取り除きます。なぜなら、より新しく、かつより大きい（または等しい） \(H_i\) が現れた時点で、それ以前の小さい値が将来最大値になることはないからです。
2. 要素の削除: ウィンドウが移動して、デックの先頭にある要素のインデックスが範囲外（\(i - K\) 以下）になった場合、先頭から取り除きます。
3. 最大値の取得: 上記の操作により、デックの先頭には常に現在のウィンドウ内での最大値のインデックスが格納されます。

最小値についても同様の操作（末尾の「 \(H_i\) 以上の値」を取り除く）を行うことで、常に先頭で最小値を管理できます。

計算量

• 時間計算量: \(O(N)\) 各要素はデックに「高々 1 回追加され、高々 1 回取り除かれる」ため、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\) 気温データを格納する配列に \(O(N)\)、デックに最大 \(O(K)\) のメモリを使用します。

実装のポイント

• デックには値を直接入れるのではなく、インデックスを入れる: ウィンドウの範囲外になったかどうかを判定するために、インデックスを保持するのが一般的です。

• 初期化: ウィンドウのサイズが \(K\) に達するまでは最大値・最小値の計算を行わず、デックの更新のみを行います。

• Python の collections.deque: Python でデックを扱う際は、標準ライブラリの collections.deque を使うことで、先頭と末尾の操作を \(O(1)\) で行えます。

  ソースコード

import sys
from collections import deque

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    H = list(map(int, input_data[2:]))

    # スライディングウィンドウ内での最大値と最小値を管理するためのデック
    max_dq = deque()
    min_dq = deque()
    
    max_range = 0
    
    for i in range(N):
        # 最大値を管理するデックの更新
        while max_dq and H[max_dq[-1]] <= H[i]:
            max_dq.pop()
        max_dq.append(i)
        # ウィンドウの範囲外になった要素を削除
        if max_dq[0] <= i - K:
            max_dq.popleft()
            
        # 最小値を管理するデックの更新
        while min_dq and H[min_dq[-1]] >= H[i]:
            min_dq.pop()
        min_dq.append(i)
        # ウィンドウの範囲外になった要素を削除
        if min_dq[0] <= i - K:
            min_dq.popleft()
            
        # ウィンドウのサイズがKに達した時点から変動幅を計算
        if i >= K - 1:
            current_max = H[max_dq[0]]
            current_min = H[min_dq[0]]
            diff = current_max - current_min
            if diff > max_range:
                max_range = diff
                
    # 結果の出力
    print(max_range)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。