概要

連続する \(K\) 日間の気温データにおいて、最高気温と最低気温の差（変動幅）が最大となる区間を見つける問題です。スライディングウィンドウと単調キューを組み合わせて効率的に解きます。

考察

素朴なアプローチとその問題点

最も単純な方法は、すべての連続 \(K\) 日間について、それぞれ最大値と最小値を求めることです。

• 連続 \(K\) 日間の区間は全部で \(N - K + 1\) 個
• 各区間で最大・最小を求めるのに \(O(K)\)
• 合計 \(O((N-K+1) \times K) = O(NK)\)

\(N = 2 \times 10^5\) の場合、最悪で \(10^{10}\) 程度の計算量となり、TLE（時間超過）になります。

重要な気づき

ウィンドウを1つずらすとき、1つの要素が追加され、1つの要素が削除されるだけです。この性質を活かせば、毎回全要素を見直す必要はありません。

解決策：単調キュー（Monotonic Deque）

単調キューは、スライディングウィンドウ内の最大値・最小値を \(O(1)\)（償却）で取得できるデータ構造です。

最大値用キュー（降順）の動作例： 配列 [3, 1, 4, 1, 5], \(K = 3\) の場合

ステップ	追加要素	キューの状態（インデックス）	ウィンドウの最大値
i=0	3	[0]	-
i=1	1	[0, 1]	-
i=2	4	2	4
i=3	1	[2, 3]	4
i=4	5	4	5

アルゴリズム

1. 2つの単調キューを用意

   • max_deque: 最大値を管理（値が降順になるよう維持）
   • min_deque: 最小値を管理（値が昇順になるよう維持）

2. 各要素を順に処理

   • 新しい要素を追加する際、キューの末尾から不要な要素を削除
     • max_deque: 新しい要素以下のものを削除
     • min_deque: 新しい要素以上のものを削除
   • インデックスをキューに追加

3. ウィンドウサイズが \(K\) に達したら

   • キューの先頭がウィンドウ外なら削除
   • max_deque[0] が最大値、min_deque[0] が最小値のインデックス
   • 変動幅 = 最大値 - 最小値 を計算し、答えを更新

計算量

• 時間計算量: \(O(N)\)

  • 各要素はキューに最大1回追加され、最大1回削除される
  • 全体で \(O(N)\) の操作

• 空間計算量: \(O(K)\)

  • 各キューには最大 \(K\) 個の要素が入る

実装のポイント

1. インデックスを格納する

   • キューには値ではなくインデックスを格納します。これにより、要素がウィンドウ内にあるかどうかを判定できます。

2. ウィンドウ外の要素の削除タイミング

   • キューの先頭がウィンドウ外（index < i - K + 1）になったら削除します。

3. 等号の扱い

   • max_deque では <= で削除（同じ値なら新しい方を残す）

   • min_deque では >= で削除（同じ値なら新しい方を残す）

   • これにより、同じ値が複数あっても正しく動作します。

     ソースコード

from collections import deque

def solve():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    # スライディングウィンドウで最大値と最小値を効率的に管理する
    # 単調キュー（Monotonic Deque）を使用
    
    max_deque = deque()  # 最大値を管理（降順）
    min_deque = deque()  # 最小値を管理（昇順）
    
    max_variation = 0
    
    for i in range(N):
        # 新しい要素を追加
        # max_deque: 後ろから、現在の要素より小さいものを削除
        while max_deque and H[max_deque[-1]] <= H[i]:
            max_deque.pop()
        max_deque.append(i)
        
        # min_deque: 後ろから、現在の要素より大きいものを削除
        while min_deque and H[min_deque[-1]] >= H[i]:
            min_deque.pop()
        min_deque.append(i)
        
        # ウィンドウサイズがKになったら
        if i >= K - 1:
            # ウィンドウ外の要素を前から削除
            while max_deque[0] < i - K + 1:
                max_deque.popleft()
            while min_deque[0] < i - K + 1:
                min_deque.popleft()
            
            # 現在のウィンドウの変動幅を計算
            current_max = H[max_deque[0]]
            current_min = H[min_deque[0]]
            variation = current_max - current_min
            
            max_variation = max(max_variation, variation)
    
    print(max_variation)

solve()

---

この解説は claude4.5opus によって生成されました。