Overview

Given temperature data over consecutive days, find the maximum temperature fluctuation range (difference between the highest and lowest temperatures) among all windows of \(K\) consecutive days.

Analysis

This problem involves sliding a window of length \(K\) from left to right and finding the maximum difference between the maximum and minimum values within each window.

Naive Approach and Its Issues

For example, if we simply perform a linear search for the maximum and minimum values in each window, the time complexity becomes \(O(N \cdot K)\). Given the constraints where \(N\) and \(K\) can be up to \(2 \times 10^5\), the worst case would require \(4 \times 10^{10}\) operations, which clearly exceeds the time limit (TLE).

Key Idea for an Efficient Solution

Therefore, we need a way to efficiently retrieve and update the maximum and minimum values within the sliding window. This can be achieved efficiently using the sliding window minimum/maximum management technique with a deque.

Specifically: - The deque for maintaining the maximum is managed so that elements are in descending order - The deque for maintaining the minimum is managed so that elements are in ascending order

This ensures that the front of each deque always holds the current window’s maximum or minimum value.

Algorithm

1. Read the input (\(N\), \(K\), and the temperature \(H\) for each day).
2. Prepare two deques:
   • max_deque: candidates for the maximum value in the current window (stores indices)
   • min_deque: candidates for the minimum value in the current window (stores indices)
3. For each day \(i = 0\) to \(N-1\), repeat the following:
   • Update max_deque and min_deque by inserting the current temperature \(H[i]\) at the appropriate position
   • Remove indices from the deques that are outside the window
   • Once the window size reaches \(K\), retrieve the maximum and minimum values from max_deque[0] and min_deque[0], and compute the fluctuation range
   • Update the maximum fluctuation range

In this way, we can efficiently obtain the maximum and minimum for every window of \(K\) consecutive days.

Complexity

• Time complexity: \(O(N)\)
  Each element is added to and removed from the deque exactly once, resulting in a total of \(O(N)\)
• Space complexity: \(O(K)\)
  The deque contains at most \(K\) elements

Implementation Notes

• By storing “indices” rather than temperature values in the deques, we can easily determine whether an element is outside the window

• When updating the deques, appropriately pop elements from the back when a new value is inserted (to maintain monotonicity)

• Be careful not to compute the fluctuation range until the window size reaches \(K\)

  Source Code

from collections import deque
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    H = list(map(int, data[2:]))

    # Deque for maintaining max and min in sliding window
    max_deque = deque()
    min_deque = deque()
    
    max_diff = 0

    for i in range(N):
        # Add current element to deques
        while max_deque and H[max_deque[-1]] <= H[i]:
            max_deque.pop()
        max_deque.append(i)
        
        while min_deque and H[min_deque[-1]] >= H[i]:
            min_deque.pop()
        min_deque.append(i)
        
        # Remove elements out of the window
        while max_deque and max_deque[0] <= i - K:
            max_deque.popleft()
        while min_deque and min_deque[0] <= i - K:
            min_deque.popleft()
        
        # Start calculating once we have a full window
        if i >= K - 1:
            current_diff = H[max_deque[0]] - H[min_deque[0]]
            if current_diff > max_diff:
                max_diff = current_diff
                
    print(max_diff)

if __name__ == "__main__":
    main()

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