Overview

This problem asks us to find the length of the longest interval of consecutive days where the difference between the maximum and minimum temperatures is at most \(K\). We solve it efficiently by combining the two-pointer technique (sliding window) with a Monotonic Deque.

Analysis

Problem Reformulation

Find the longest contiguous subarray of array \(A\) that satisfies \(\max - \min \leq K\).

Naive Approach and Its Issues

Consider trying all intervals \([l, r]\) and computing the maximum and minimum for each interval. - Number of ways to choose an interval: \(O(N^2)\) - Computing max and min for each interval: \(O(N)\) - Total: \(O(N^3)\)

This is far too slow for \(N = 2 \times 10^5\).

Key Insights

1. Condition for using the two-pointer technique: If interval \([l, r]\) satisfies the condition, then any shorter interval \([l', r']\) (where \(l \leq l' \leq r' \leq r\)) also satisfies the condition. In other words, for a fixed \(r\), there exists a minimum \(l\) that satisfies the condition, and as \(r\) increases, \(l\) also increases monotonically.

2. Efficiently managing interval max and min: In the two-pointer technique, we move the interval endpoints one at a time. By using a monotonic deque, we can update the interval’s maximum and minimum values in \(O(1)\) (amortized) time.

Algorithm

What is a Monotonic Deque?

• Deque for maximum: Maintains values in monotonically decreasing order. The front is always the maximum.
• Deque for minimum: Maintains values in monotonically increasing order. The front is always the minimum.

Processing Flow

1. Advance the right endpoint right from 0 to \(N-1\) in order
2. When adding right, update the deques to maintain monotonicity
3. While maximum - minimum \(> K\), advance the left endpoint left
4. Remove indices before left from the deques
5. Record the maximum interval length right - left + 1

Concrete Example

For \(A = [3, 1, 4, 1, 5]\), \(K = 2\):

right	interval	max	min	diff	condition	length
0	[3]	3	3	0	○	1
1	[3,1]	3	1	2	○	2
2	[3,1,4]	4	1	3	× → left=1 → [1,4]	2
3	[1,4,1]	4	1	3	× → left=2 → [4,1] → × → left=3 → [1]	1
4	[1,5]	5	1	4	× → left=4 → [5]	1

Answer: 2

Complexity

• Time Complexity: \(O(N)\)
  • Each element is added to the deque at most once and removed at most once
  • Both left and right are monotonically increasing, with a total of \(O(N)\) moves
• Space Complexity: \(O(N)\)
  • Each of the two deques holds at most \(N\) elements

Implementation Notes

1. Store indices in the deques: By storing indices rather than the values themselves, we can determine when to remove elements that are before left

2. Order of monotonic deque updates:

   • First, add the element at right (removing elements from the back that break monotonicity)
   • Then check the condition → advance left → remove out-of-range elements from the front

3. Preventing access to empty deques: In the while condition, check max_deque and min_deque before accessing the front element

Source Code

from collections import deque

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    if N == 0:
        print(0)
        return
    
    # Two-pointer technique + monotonic deque to manage interval max/min
    max_deque = deque()  # Manages maximum (monotonically decreasing)
    min_deque = deque()  # Manages minimum (monotonically increasing)
    
    left = 0
    ans = 0
    
    for right in range(N):
        # Add to max_deque (maintain monotonically decreasing order)
        while max_deque and A[max_deque[-1]] <= A[right]:
            max_deque.pop()
        max_deque.append(right)
        
        # Add to min_deque (maintain monotonically increasing order)
        while min_deque and A[min_deque[-1]] >= A[right]:
            min_deque.pop()
        min_deque.append(right)
        
        # While condition is not satisfied, advance left
        while max_deque and min_deque and A[max_deque[0]] - A[min_deque[0]] > K:
            left += 1
            # Remove indices before left from the deques
            while max_deque and max_deque[0] < left:
                max_deque.popleft()
            while min_deque and min_deque[0] < left:
                min_deque.popleft()
        
        # Update the current interval length
        ans = max(ans, right - left + 1)
    
    print(ans)

solve()

---

This editorial was generated by claude4.5opus.