概要

連続する \(K\) 日間の気温データから、最大の気温変動幅（最高気温と最低気温の差）を求めます。

考察

この問題は、長さ \(K\) のスライディングウィンドウを左から右へ動かしながら、各ウィンドウ内の最大値と最小値の差の最大値を求める問題です。

素朴な解法とその問題点

例えば、各ウィンドウに対して単純に最大値と最小値を線形探索で求めると、時間計算量は \(O(N \cdot K)\) になります。制約より \(N\) や \(K\) が最大で \(2 \times 10^5\) になるため、最悪ケースで \(4 \times 10^{10}\) 回の計算となり、明らかに時間内に収まりません（TLE）。

効率的な解法の着想

そこで、スライディングウィンドウ内で最大値と最小値を高速に取得・更新する必要が出てきます。これは deque を用いたスライディングウィンドウの最小値・最大値管理テクニック で効率的に実現できます。

具体的には、 - 最大値を保持する deque は、要素が降順になるように管理 - 最小値を保持する deque は、要素が昇順になるように管理

これにより、deque の先頭が常に現在のウィンドウ内の最大値・最小値になります。

アルゴリズム

1. 入力を読み込みます（\(N\), \(K\), 各日ごとの気温 \(H\)）。
2. deque を二つ用意します：
   • max_deque: 現在のウィンドウ内の最大値候補（インデックスを格納）
   • min_deque: 現在のウィンドウ内の最小値候補（インデックスを格納）
3. 各日 \(i = 0\) から \(N-1\) まで以下を繰り返します：
   • max_deque および min_deque を更新して、現在の気温 \(H[i]\) を適切な位置に挿入
   • ウィンドウ外のインデックスを deque から削除
   • ウィンドウサイズが \(K\) になったら、max_deque[0] と min_deque[0] から最大値と最小値を取り出し、変動幅を計算
   • 変動幅の最大値を更新

このようにして、すべての連続する \(K\) 日間について、その区間での最大・最小を効率的に取得できます。

計算量

• 時間計算量: \(O(N)\)
  各要素は deque に一度追加され、一度削除されるため、合計で \(O(N)\)
• 空間計算量: \(O(K)\)
  deque には最大で \(K\) 個の要素が含まれる

実装のポイント

• deque には気温の値ではなく「インデックス」を格納することで、ウィンドウ外かどうかを簡単に判定できる
• deque の更新処理では、新しい値が入るときに適切に末尾を pop する（単調性を保つ）
• ウィンドウサイズが \(K\) に達するまでは変動幅を計算しないように注意

ソースコード

from collections import deque
import sys

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

    # Deque for maintaining max and min in sliding window
    max_deque = deque()
    min_deque = deque()
    
    max_diff = 0

    for i in range(N):
        # Add current element to deques
        while max_deque and H[max_deque[-1]] <= H[i]:
            max_deque.pop()
        max_deque.append(i)
        
        while min_deque and H[min_deque[-1]] >= H[i]:
            min_deque.pop()
        min_deque.append(i)
        
        # Remove elements out of the window
        while max_deque and max_deque[0] <= i - K:
            max_deque.popleft()
        while min_deque and min_deque[0] <= i - K:
            min_deque.popleft()
        
        # Start calculating once we have a full window
        if i >= K - 1:
            current_diff = H[max_deque[0]] - H[min_deque[0]]
            if current_diff > max_diff:
                max_diff = current_diff
                
    print(max_diff)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。