概要

区間内の最高気温と最低気温の差が \(K\) 以下となるような「連続区間」のうち、最長の長さを求めます。
\(N\) が最大 \(2\times 10^5\) なので、高速に区間の最大・最小を管理する必要があります。

考察

ある区間 \([l, r]\)（\(l \le r\)）が安定している条件は
$\(\max(A_l,\dots,A_r) - \min(A_l,\dots,A_r) \le K\)$ です。

素朴な方法が遅い理由

全ての \(l, r\) を試すと区間は \(O(N^2)\) 個あり、さらに各区間で最大・最小を求めると \(O(N)\) かかってしまい、最悪 \(O(N^3)\) になります。
最大・最小を事前計算しても「任意区間の max/min」を毎回更新するのが難しく、単純にやると \(O(N^2)\) から改善できません（\(N=2\times 10^5\) では TLE）。

解決の方向性（重要な気づき）

• 右端 \(r\) を 1 ずつ増やしながら「条件を満たす範囲で左端 \(l\) をできるだけ小さく保つ」= 典型的な 尺取り法（スライディングウィンドウ） が使えます。
• ただし、尺取り法の各ステップで「現在の区間の最大値・最小値」を高速に知る必要があります。
• これを 単調キュー（Monotonic Queue） で実現すると、各要素を高々 1 回ずつ追加・削除でき、全体 \(O(N)\) になります。

アルゴリズム

尺取り法で区間 \([l, r]\) を動かし、区間内の最大・最小を次の 2 つの deque で管理します。

• maxdq: 区間内の候補最大値を 大きい順（単調減少） に並べる deque
  
  • 新しい値 \(x\) を入れるとき、末尾が \(x\) より小さい間は不要なので pop する
    
  • 先頭 maxdq[0] が現在の区間の最大値になる
• mindq: 区間内の候補最小値を 小さい順（単調増加） に並べる deque
  
  • 新しい値 \(x\) を入れるとき、末尾が \(x\) より大きい間は pop する
    
  • 先頭 mindq[0] が現在の区間の最小値になる

手順： 1. \(r\) を左から右へ動かし、\(A_r\) を maxdq, mindq に追加（単調性を保つように不要な末尾を削除）。 2. もし maxdq[0] - mindq[0] > K なら条件違反なので、左端 \(l\) を右へ動かして区間を縮める。
- 縮めるとき、ちょうど区間から抜ける値 \(A_l\) が maxdq / mindq の先頭と一致していれば先頭を popleft（区間外になった最大/最小候補を消す）。 - 条件を満たすまで繰り返す。 3. 条件を満たしたら、そのときの区間長 \(r-l+1\) で答えを更新。

小さな例

\(A=[3,1,4,2],\ K=2\) のとき： - \(r\) を伸ばすと最大・最小が変わるが、maxdq[0] と mindq[0] を見るだけで差が分かる - 差が \(2\) を超えたら \(l\) を進めて調整
この「伸ばして、ダメなら縮める」を \(O(1)\) 償却で行えるのが単調キューの強みです。

計算量

• 時間計算量: \(O(N)\)
  （各要素は maxdq/mindq に高々 1 回追加され、高々 1 回削除されるため）
• 空間計算量: \(O(N)\)
  （最悪の場合、deque に要素が並ぶ）

実装のポイント

• maxdq は「末尾が小さい間 pop」して 単調減少、mindq は「末尾が大きい間 pop」して 単調増加 に保ちます。

• 左端を動かすときは、区間から出ていく値 \(A_l\) が deque の先頭と一致した場合のみ popleft() します（一致しないなら、その値は先頭ではなく既に候補から落ちている）。

• この実装では値そのものを deque に入れています。重複があっても「先頭と等しいときだけ削除」なので整合性が保てます（ただし、より一般的には添字を入れる実装もよく使われます）。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    maxdq = deque()  # decreasing
    mindq = deque()  # increasing

    l = 0
    ans = 0
    for r, x in enumerate(A):
        while maxdq and maxdq[-1] < x:
            maxdq.pop()
        maxdq.append(x)

        while mindq and mindq[-1] > x:
            mindq.pop()
        mindq.append(x)

        while maxdq[0] - mindq[0] > K:
            y = A[l]
            if maxdq[0] == y:
                maxdq.popleft()
            if mindq[0] == y:
                mindq.popleft()
            l += 1

        ans = max(ans, r - l + 1)

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。