題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 awc0065_e Period of Stable Temperature

Problem Statement

題目簡述

給定一段每天的溫度序列，若某個連續期間內的最高溫與最低溫差不超過 $D$ ，則稱這段期間是穩定的。
請找出長度至少為 $K$ 的穩定連續期間中，最長的長度；若不存在這樣的期間，輸出 $-1$ 。

Constraints

約束條件

$1 \leq N \leq 5 \times 10^5$
$1 \leq K \leq N$
$0 \leq D \leq 10^9$
$-10^9 \leq H_i \leq 10^9$ $(1 \leq i \leq N)$

思路：不定長滑動窗口 + 單調佇列

本題要找的是一段最長的連續期間，使其中最高溫與最低溫的差不超過 $D$ 。如果枚舉每個區間再重新計算最大值與最小值，需要 $O(N^2)$ 的時間，顯然是不可行的。

關鍵觀察

注意到當擴大區間時，最大值只會增加或保持不變，最小值只會減少或保持不變。
因此當右端點固定時，左端點越往右越容易合法。
這種性質非常適合用不定長滑動窗口來維護當前仍可能成為答案的連續期間。

滑動窗口本身只能控制區間範圍，還需要快速知道目前區間內的最高溫與最低溫，而這正是經典題目 239. Sliding Window Maximum 或 P1886 【模板】单调队列 / 滑动窗口的核心技巧。解法是使用 單調佇列(Monotonic Queue) 分別維護目前窗口內的最大值與最小值，讓隊首永遠是目前窗口的極值候選。

每加入一個新元素時，佇列尾端中已經不可能再成為極值的元素會被移除。這樣每個位置最多進出佇列一次，就能在整體線性時間內維護區間極值。

與固定長度窗口的差異

本題的窗口長度是不定的。當目前窗口內的最大值與最小值差距超過 $D$ 時，不能只照固定大小彈出最左端元素，而是要移動左端點直到窗口重新合法。

這裡的關鍵是每次都移除兩個隊首中下標較小的元素，因為它代表的極值出現得更早，必須先移除它才有可能讓窗口重新合法。

為什麼這樣收縮？

當最大值與最小值差距過大時，只移除中間的普通元素沒有意義，因為兩個極端值仍然同時存在，區間一定還是不合法。真正能改變狀態的是排除其中一個極端值；選擇較早出現的那個，等同於用最小幅度推進左邊界，保留最多可能延伸成長答案的元素。

複雜度分析

時間複雜度： $\mathcal{O}(N)$
空間複雜度： $\mathcal{O}(N)$

Code

from collections import deque


def solve():
    n, k, d = map(int, input().split())
    A = list(map(int, input().split()))

    # 滑動窗口最大值/最小值
    ans = -1
    q_mx = deque()
    q_mn = deque()
    left = 0
    for i, x in enumerate(A):
        # 1. 入窗口
        while q_mx and A[q_mx[-1]] < x:
            q_mx.pop()
        q_mx.append(i)
        while q_mn and A[q_mn[-1]] > x:
            q_mn.pop()
        q_mn.append(i)

        # 2. 差值太大，需要出窗口
        while A[q_mx[0]] - A[q_mn[0]] > d:
            if q_mx[0] < q_mn[0]:
                left = q_mx.popleft() + 1
            else:
                left = q_mn.popleft() + 1

        # 3. 更新答案
        if i - left + 1 >= k:
            ans = max(ans, i - left + 1)
    print(ans)


if __name__ == "__main__":
    solve()