概要

\(N\) 日間の気温データから、連続する \(K\) 日以上で気温の最大値と最小値の差が \(D\) 以下である最長の期間の日数を求めます。

考察

この問題では、「連続する区間」かつ「最大値と最小値の差が \(D\) 以下」という条件を満たす最長の区間を探す必要があります。

素朴な方法として、全ての区間を全探索して条件をチェックする方法があります。しかし、\(N\) が最大で \(5 \times 10^5\) なので、\(O(N^2)\) の計算量では時間内に処理できません（TLE）。

そこで、「スライディングウィンドウ（しゃくとり法）」の考えを使います。区間の右端を伸ばしながら、その区間内の最大値と最小値を高速に管理できるようにすれば、効率良く探索できます。

さらに、区間の最大値・最小値を高速に取得するために、双方向キュー（deque） を用いてデータを管理します。これにより、最大値・最小値を常に \(O(1)\) で取得でき、全体でも各要素を一度ずつしか処理しないため、線形時間で解くことができます。

アルゴリズム

1. 左右のポインタ left, right を使ってスライディングウィンドウを管理します。
2. min_deque には最小値候補のインデックスを保持し、先頭が現在の区間での最小値となるようにします。
3. max_deque には最大値候補のインデックスを保持し、先頭が現在の区間での最大値となるようにします。
4. right を進めながら以下の処理を行います：
   • 新しい要素をそれぞれの deque に適切に追加（不要な要素は削除）
   • 区間の最大値と最小値の差が \(D\) を超えていたら、left を進めながら条件を満たすまで縮めます。
   • 現在の区間が \(K\) 日以上であれば、最大日数を更新します。

このようにして、最長の安定期間を効率よく求めます。

具体例

例えば、入力が以下の場合：

N=6, K=3, D=2
H = [1, 3, 2, 4, 3, 2]

スライディングウィンドウを進めると、区間 [1, 3, 2, 4] （index 0〜3）の最大値は4、最小値は1、差は3となり \(D=2\) を超えるので縮めます。最終的に [3, 2, 4, 3]（index 1〜4）などの中で最も長い安定期間を探します。

計算量

• 時間計算量: \(O(N)\)
  • 各要素は deque に高々1回追加・削除されるため、全体で線形時間。
• 空間計算量: \(O(N)\)
  • deque に最大で \(N\) 個のインデックスを格納する可能性がある。

実装のポイント

• deque にはインデックスを保持することで、古い要素を適切に削除できる。

• 最大値・最小値の差が条件を超えた場合、left を進める処理を忘れずに。

• 区間長が \(K\) 未満のときは答えを更新しないことに注意。

  ソースコード

import sys
from collections import deque

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

    # スライディングウィンドウで最小値・最大値を効率的に管理するためのdeque
    min_deque = deque()  # (index, value) のインデックスを保持（単調増加）
    max_deque = deque()  # (index, value) のインデックスを保持（単調減少）

    left = 0
    max_len = -1

    for right in range(N):
        # min_deque の末尾に新しい要素を追加する際に不要なものを削除
        while min_deque and H[min_deque[-1]] >= H[right]:
            min_deque.pop()
        min_deque.append(right)

        # max_deque の末尾に新しい要素を追加する際に不要なものを削除
        while max_deque and H[max_deque[-1]] <= H[right]:
            max_deque.pop()
        max_deque.append(right)

        # ウィンドウ内の最大値と最小値の差がD以下か確認
        while min_deque and max_deque and H[max_deque[0]] - H[min_deque[0]] > D:
            # 条件を満たさないのでleftを進める
            if min_deque[0] == left:
                min_deque.popleft()
            if max_deque[0] == left:
                max_deque.popleft()
            left += 1

        # 現在のウィンドウサイズがK以上なら更新
        current_len = right - left + 1
        if current_len >= K:
            max_len = max(max_len, current_len)

    print(max_len)

if __name__ == "__main__":
    main()

---

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