Overview

Given consecutive days of temperature data, the problem asks to find the maximum length of a consecutive period where the difference between the maximum and minimum values is at most \(D\) and the length is at least \(K\).

Analysis

This problem requires efficiently managing the maximum and minimum values within a sliding window. A naive approach that examines all consecutive intervals takes \(O(N^2)\) time, which is too slow given that \(N\) can be up to \(500,000\). Therefore, the classic technique for the sliding window max/min problem using double-ended queues (deques) is effective.

Algorithm

1. Sliding Window and Deques: The window is represented by a left pointer left and a right pointer right. As right moves from 0 to \(N-1\), the maximum and minimum values within the current window \([left, right]\) are managed using max_deque and min_deque, respectively.
2. Managing the Maximum Queue (max_deque): When advancing right, if there are values at the back of the queue smaller than the current value \(H[\text{right}]\), they are removed before adding right. This maintains the queue in descending order.
3. Managing the Minimum Queue (min_deque): Similarly, if there are values at the back of the queue larger than the current value \(H[\text{right}]\), they are removed before adding right. This maintains the queue in ascending order.
4. Condition Check and Left Pointer Adjustment: If the difference between the maximum value (max_deque[0]) and the minimum value (min_deque[0]) in the current window exceeds \(D\), advance left to shrink the window. At this point, if left matches the front of either queue, remove it from that queue as well.
5. Recording Valid Intervals: Once the window satisfies the condition, check whether its length is at least \(K\), and update the maximum length accordingly.

Complexity

• Time complexity: \(O(N)\)
  • Each element is operated on at most twice (one addition and one removal), so the overall complexity is \(O(N)\).
• Space complexity: \(O(N)\)
  • This accounts for the two deques and the input storage, totaling \(O(N)\).

Implementation Notes

• Store indices in the deques, and properly remove indices that fall outside the current window range.

• When shrinking the window, check whether the front of each queue matches left and remove it before incrementing left.

• Confirm that the length of a qualifying interval is at least \(K\) before updating the maximum length.

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0]); K = int(data[1]); D = int(data[2])
    H = list(map(int, data[3:3+n]))
    
    max_len = -1
    left = 0
    max_deque = deque()
    min_deque = deque()
    
    for right in range(n):
        while max_deque and H[max_deque[-1]] <= H[right]:
            max_deque.pop()
        max_deque.append(right)
        
        while min_deque and H[min_deque[-1]] >= H[right]:
            min_deque.pop()
        min_deque.append(right)
        
        while left <= right and H[max_deque[0]] - H[min_deque[0]] > D:
            if max_deque[0] == left:
                max_deque.popleft()
            if min_deque[0] == left:
                min_deque.popleft()
            left += 1
            
        length = right - left + 1
        if length >= K:
            if length > max_len:
                max_len = length
                
    print(max_len if max_len != -1 else -1)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.