Overview

Given \(N\) days of temperature data, find the length of the longest period of \(K\) or more consecutive days where the difference between the maximum and minimum temperatures is at most \(D\).

Analysis

In this problem, we need to find the longest interval that satisfies both conditions: “consecutive days” and “the difference between the maximum and minimum values is at most \(D\).”

A naive approach would be to enumerate all intervals and check the condition for each. However, since \(N\) can be up to \(5 \times 10^5\), an \(O(N^2)\) approach cannot finish within the time limit (TLE).

Therefore, we use the idea of a sliding window (two-pointer technique). By extending the right end of the interval while efficiently maintaining the maximum and minimum values within the interval, we can search efficiently.

Furthermore, to quickly retrieve the maximum and minimum of the interval, we use double-ended queues (deques) to manage the data. This allows us to always retrieve the maximum and minimum in \(O(1)\), and since each element is processed only once overall, we can solve the problem in linear time.

Algorithm

1. Use left and right pointers left, right to manage the sliding window.
2. min_deque holds indices of minimum value candidates, with the front always being the minimum of the current interval.
3. max_deque holds indices of maximum value candidates, with the front always being the maximum of the current interval.
4. While advancing right, perform the following operations:
   • Appropriately add the new element to each deque (removing unnecessary elements).
   • If the difference between the maximum and minimum of the interval exceeds \(D\), advance left and shrink the interval until the condition is satisfied.
   • If the current interval is \(K\) or more days long, update the maximum number of days.

In this way, we efficiently find the longest stable period.

Concrete Example

For example, given the following input:

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

As the sliding window advances, the interval [1, 3, 2, 4] (index 0 to 3) has a maximum of 4, a minimum of 1, and a difference of 3, which exceeds \(D=2\), so we shrink the window. Ultimately, we search for the longest stable period among intervals such as [3, 2, 4, 3] (index 1 to 4).

Complexity

• Time complexity: \(O(N)\)
  • Each element is added to and removed from the deque at most once, so the overall time is linear.
• Space complexity: \(O(N)\)
  • The deques may store up to \(N\) indices.

Implementation Notes

• By storing indices in the deques, we can properly remove outdated elements.

• Don’t forget to advance left when the difference between the maximum and minimum exceeds the condition.

• Be careful not to update the answer when the interval length is less than \(K\).

  Source Code

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()

---

This editorial was generated by qwen3-coder-480b.