概要

連続する日数の気温データから、最大値と最小値の差が \(D\) 以下であり、かつ長さが \(K\) 以上であるような連続する期間の最大長を求める問題です。

考察

この問題は、スライディングウィンドウ内の最大値と最小値を効率的に管理する必要があります。素朴なアプローチでは、すべての連続する区間を調べると \(O(N^2)\) の時間がかかり、\(N\) が最大 \(500,000\) であるため実行時間制限に間に合いません。そこで、スライディングウィンドウ最大値最小値問題の典型手法である、両端キュー（deque）を使用した解法が有効です。

アルゴリズム

1. スライディングウィンドウと両端キュー: 左ポインタ left と右ポインタ right でウィンドウを表現します。right を 0 から \(N-1\) まで動かしながら、現在のウィンドウ \([left, right]\) 内の最大値と最小値をそれぞれ max_deque と min_deque で管理します。
2. 最大値キュー（max_deque）の管理: right を進める際に、現在の値 \(H[\text{right}]\) より小さい値がキューの末尾にある場合は、それらを削除してから right を追加します。これにより、キューは降順になるよう維持されます。
3. 最小値キュー（min_deque）の管理: 同様に、現在の値 \(H[\text{right}]\) より大きい値がキューの末尾にある場合は、それらを削除してから right を追加します。これにより、キューは昇順になるよう維持されます。
4. 条件チェックと左ポインタの調整: 現在のウィンドウ内の最大値（max_deque[0]）と最小値（min_deque[0]）の差が \(D\) より大きい場合、left を進めてウィンドウを縮めます。このとき、left が各キューの先頭と一致する場合は、キューからも削除します。
5. 有効な区間の記録: ウィンドウが条件を満たしたら、その長さが \(K\) 以上かチェックし、最大長を更新します。

計算量

• 時間計算量: \(O(N)\)
  • 各要素は最大2回（追加と削除）しか操作されないため、全体で \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • 2つの両端キューと入力を格納するため、\(O(N)\) です。

実装のポイント

• 両端キューにはインデックスを格納し、現在のウィンドウ範囲外のインデックスを適切に削除します。

• ウィンドウを縮める際は、left をインクリメントする前に、各キューの先頭が left と一致するかチェックして削除します。

• 条件を満たす区間の長さが \(K\) 以上であることを確認してから最大長を更新します。

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0]); K = int(data[1]); D = int(data[2])
    H = list(map(int, data[3:3+n]))
    
    max_len = -1
    left = 0
    max_deque = deque()
    min_deque = deque()
    
    for right in range(n):
        while max_deque and H[max_deque[-1]] <= H[right]:
            max_deque.pop()
        max_deque.append(right)
        
        while min_deque and H[min_deque[-1]] >= H[right]:
            min_deque.pop()
        min_deque.append(right)
        
        while left <= right and H[max_deque[0]] - H[min_deque[0]] > D:
            if max_deque[0] == left:
                max_deque.popleft()
            if min_deque[0] == left:
                min_deque.popleft()
            left += 1
            
        length = right - left + 1
        if length >= K:
            if length > max_len:
                max_len = length
                
    print(max_len if max_len != -1 else -1)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。