Overview

Find the length of the longest contiguous interval of dates such that the difference between the maximum and minimum temperatures within that interval is at most \(K\).

Analysis

In this problem, we need to find the longest interval that satisfies two conditions: it must be a “contiguous interval” and “the difference between the maximum and minimum values within the interval must be at most \(K\)”.

Naive Approach and Its Issues

For example, one could enumerate all intervals \([l, r]\) and compute the maximum and minimum values for each one. However, the time complexity of this approach is \(O(N^3)\), which is far too slow given the constraint \(N \leq 2 \times 10^5\).

To be more efficient, we consider using the two-pointer technique (sliding window). In this technique, we manage the interval by extending the right endpoint while appropriately shrinking the left endpoint. However, even with a simple two-pointer approach, if we recompute the maximum and minimum of the interval each time, it becomes \(O(N^2)\).

Solution: Fast Maximum/Minimum Management Using Deque

To efficiently retrieve and update the maximum and minimum of the interval, we use a monotonic deque.

• The deque for maintaining the maximum is managed in monotonically decreasing order (the front is the maximum)
• The deque for maintaining the minimum is managed in monotonically increasing order (the front is the minimum)

This allows us to retrieve the maximum and minimum of the interval in \(O(1)\), and deque updates are performed in amortized \(O(1)\), making the overall algorithm fast.

Algorithm

1. Manage the sliding window using left and right pointers left and right.
2. For each right:
   • Update max_deque and min_deque by inserting the current element at the appropriate position
   • If the difference between the maximum and minimum of the interval [left, right] exceeds \(K\), advance left while adjusting the deques until the condition is satisfied
   • If the condition is satisfied, record the interval length right - left + 1
3. Output the maximum length obtained overall

Example

Sample input:

6 2
1 3 2 4 3 5

• Interval [1, 3, 2] → max: 3, min: 1 → difference: 2 (OK)
• Interval [1, 3, 2, 4] → max: 4, min: 1 → difference: 3 (NG) → advance left

In this way, whenever an interval that does not satisfy the condition appears, we advance the left endpoint, so we always manage only valid intervals.

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 deque stores at most \(N\) indices.

Implementation Notes

• Storing indices in the deque makes it convenient when removing old elements
• When the front of the deque falls outside the current interval, remove it promptly with popleft()
• When checking whether the difference between the maximum and minimum satisfies the condition, make sure the deque is not empty

## Source Code

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

---

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