Overview

This problem asks us to find the longest period of at least \(K\) consecutive days where the difference between the maximum and minimum temperatures is at most \(D\). We solve it efficiently by combining the two-pointer (sliding window) technique with monotonic deques.

Analysis

Naive Approach

If we try all contiguous intervals \([l, r]\) and compute the maximum and minimum for each, the number of interval choices is \(O(N^2)\) and computing the max/min for each interval takes \(O(N)\), resulting in \(O(N^3)\) overall. This is far too slow for \(N = 5 \times 10^5\).

Key Observations

1. Expanding an interval can only increase the difference: If an interval \([l, r]\) is stable (max - min \(\leq D\)), then shrinking this interval preserves stability. Conversely, expanding it may increase the difference. This monotonicity is the basis for applying the two-pointer technique.

2. Two-pointer (sliding window) technique: By advancing the right endpoint \(r\) one step at a time and advancing the left endpoint \(l\) to restore the condition whenever it is violated, we can efficiently examine all intervals.

3. Fast maintenance of interval max/min: As we slide the window using the two-pointer technique, we need to retrieve the interval’s maximum and minimum in \(O(1)\). This can be achieved using monotonic deques.

Concrete Example

For example, with \(H = [3, 1, 4, 1, 5]\), \(K = 2\), \(D = 2\):

• \([l=0, r=0]\): \(\{3\}\) → difference \(0 \leq 2\) ✓, length \(1 < K\)
• \([l=0, r=1]\): \(\{3,1\}\) → difference \(2 \leq 2\) ✓, length \(2 \geq K\) → candidate answer \(2\)
• \([l=0, r=2]\): \(\{3,1,4\}\) → difference \(3 > 2\) ✗ → advance \(l\)
• \([l=1, r=2]\): \(\{1,4\}\) → difference \(3 > 2\) ✗ → advance \(l\)
• \([l=2, r=2]\): \(\{4\}\) → difference \(0 \leq 2\) ✓, length \(1 < K\)
• …and so on.

Algorithm

1. Max deque (descending order): The front of the deque always holds the index of the maximum value in the current window \([l, r]\). When adding a new element, remove elements from the back that are less than or equal to the new element.

2. Min deque (ascending order): The front of the deque always holds the index of the minimum value in the current window \([l, r]\). When adding a new element, remove elements from the back that are greater than or equal to the new element.

3. Two-pointer flow:

   • Advance \(r\) from \(0\) to \(N-1\).
   • Each time \(r\) is added, update both deques.
   • While the window’s maximum \(-\) minimum exceeds \(D\), advance \(l\) by \(1\) and remove the front of either deque if it has fallen outside the window.
   • If the window length \(r - l + 1 \geq K\), update the answer candidate.

4. If no candidate is found at the end, output \(-1\).

Complexity

• Time complexity: \(O(N)\) — Each element is added to and removed from the deque at most once, so the overall work is linear.
• Space complexity: \(O(N)\) — For the deques and the input array.

Implementation Notes

• Store indices rather than values in the deques. This way, when advancing the left endpoint \(l\), we can check whether the front of the deque has fallen outside the window using max_deque[0] < l.

• When advancing \(l\) in the while loop, we need to check the fronts of both the max deque and the min deque before re-checking the condition.

• By initializing the answer to \(-1\), if no stable period of at least \(K\) days is ever found, \(-1\) is output as-is.

  Source Code

from collections import deque
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    D = int(input_data[2])
    H = [int(input_data[3 + i]) for i in range(N)]
    
    # Two pointers with monotonic deques for max and min
    max_deque = deque()  # decreasing
    min_deque = deque()  # increasing
    
    ans = -1
    l = 0
    
    for r in range(N):
        # Maintain max deque (decreasing)
        while max_deque and H[max_deque[-1]] <= H[r]:
            max_deque.pop()
        max_deque.append(r)
        
        # Maintain min deque (increasing)
        while min_deque and H[min_deque[-1]] >= H[r]:
            min_deque.pop()
        min_deque.append(r)
        
        # Shrink window from left if not stable
        while H[max_deque[0]] - H[min_deque[0]] > D:
            l += 1
            if max_deque[0] < l:
                max_deque.popleft()
            if min_deque[0] < l:
                min_deque.popleft()
        
        # Current window is [l, r], length = r - l + 1
        length = r - l + 1
        if length >= K:
            if ans < length:
                ans = length
    
    print(ans)

main()

This editorial was generated by claude4.6opus-thinking.