概要

連続した日付の区間で、その区間内の最高気温と最低気温の差が \(K\) 以下であるような最長の区間の長さを求めます。

考察

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

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

例えば、全ての区間 \([l, r]\) を全探索して、それぞれについて最大値と最小値を毎回計算する方法があります。しかし、この方法の時間計算量は \(O(N^3)\) となり、制約 \(N \leq 2 \times 10^5\) では到底間に合いません。

もう少し効率よくするために、尺取り法（スライディングウィンドウ）を使うことを考えます。尺取り法では、右端を伸ばしながら左端を適宜縮めるという形で区間を管理します。しかし、単純に尺取り法を使っても、区間の最大値・最小値を毎回再計算していると \(O(N^2)\) になってしまいます。

解決策：Deque を使った高速な最大値・最小値管理

そこで、区間の最大値と最小値を効率的に取得・更新するために、単調キュート（deque） を使用します。

• 最大値を保持する deque は、単調減少になるように管理（先頭が最大）
• 最小値を保持する deque は、単調増加になるように管理（先頭が最小）

これにより、区間の最大値・最小値を \(O(1)\) で取得でき、deque の更新も amortized \(O(1)\) で行えるため、全体として高速に動作します。

アルゴリズム

1. 左右のポインタ left, right を使ってスライディングウィンドウを管理します。
2. 各 right に対して：
   • max_deque と min_deque を更新して、現在の要素を適切な位置に挿入
   • 区間 [left, right] の最大値と最小値の差が \(K\) を超えていたら、left を進めながら条件を満たすまで deque を調整
   • 条件を満たしていれば、区間の長さ right - left + 1 を記録
3. 全体で得られた最大の長さを出力

例

入力例：

6 2
1 3 2 4 3 5

• 区間 [1, 3, 2] → 最大:3、最小:1 → 差:2（OK）
• 区間 [1, 3, 2, 4] → 最大:4、最小:1 → 差:3（NG）→ left を進める

このように、条件を満たさない区間が現れたら左端を進めることで、常に有効な区間だけを管理できます。

計算量

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

実装のポイント

• deque にはインデックスを格納することで、古い要素を削除するときに便利
• deque の先頭が区間外になった場合は適時 popleft() で取り除く
• 最大値・最小値の差が条件を満たすかどうかをチェックする際に、deque が空でないことを確認すること

## ソースコード

```python
from collections import deque

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

    # スライディングウィンドウで解く
    max_deque = deque()  # 現在の区間での最大値のインデックスを保持（単調減少）
    min_deque = deque()  # 現在の区間での最小値のインデックスを保持（単調増加）

    left = 0
    max_length = 0

    for right in range(N):
        # max_deque を更新
        while max_deque and A[max_deque[-1]] <= A[right]:
            max_deque.pop()
        max_deque.append(right)

        # min_deque を更新
        while min_deque and A[min_deque[-1]] >= A[right]:
            min_deque.pop()
        min_deque.append(right)

        # 区間 [left, right] の最大値と最小値の差が K 以下か確認
        while max_deque and min_deque and A[max_deque[0]] - A[min_deque[0]] > K:
            # 条件を満たさないので left を進める
            if max_deque[0] == left:
                max_deque.popleft()
            if min_deque[0] == left:
                min_deque.popleft()
            left += 1

        # 現在の区間 [left, right] は条件を満たすので長さを更新
        max_length = max(max_length, right - left + 1)

    print(max_length)

if __name__ == "__main__":
    main()

---

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