Overview

Given temperature data over \(N\) days, the problem asks to find the maximum value of “the difference between the highest and lowest temperatures” when choosing any consecutive \(K\) days.

Analysis

The key to this problem lies in “how to efficiently find the maximum and minimum values within a sliding window of length \(K\)”.

Naive Approach

What happens if we compute the maximum and minimum values each time for the \(K\) days starting from day \(i\)? - Number of window starting positions: \(N - K + 1\) - Searching for max and min within each window: \(O(K)\)

The overall time complexity becomes \(O(N \times K)\). Looking at the constraints, since \(N, K \leq 2 \times 10^5\), the worst case requires approximately \(4 \times 10^{10}\) computations, which will not fit within the time limit (typically about 2 seconds) and results in TLE.

Efficient Approach

When sliding the window one day at a time, most elements are shared between consecutive windows. We need a method that exploits this property to update the maximum and minimum values quickly. This is achieved by an algorithm called “Sliding Window Minimum (Maximum)”, which uses a deque (double-ended queue) to efficiently manage the values within each window.

Algorithm

Using deques, we always maintain “candidates for the maximum value” and “candidates for the minimum value” within the window. We will explain using the deque that manages the maximum value as an example.

1. Adding an element: When adding the temperature \(H_i\) of a new day, remove all values from the back of the deque that are “less than or equal to \(H_i\)”. This is because once a newer and larger (or equal) \(H_i\) appears, the smaller values before it can never become the maximum in the future.
2. Removing an element: When the window moves and the index of the element at the front of the deque becomes out of range (i.e., \(i - K\) or less), remove it from the front.
3. Retrieving the maximum: Due to the above operations, the front of the deque always stores the index of the maximum value within the current window.

For the minimum value, the same approach applies (removing values from the back that are “greater than or equal to \(H_i\)”), allowing us to always manage the minimum value at the front.

Complexity

• Time complexity: \(O(N)\) Each element is “added to the deque at most once and removed at most once,” so the overall complexity is \(O(N)\).
• Space complexity: \(O(N)\) \(O(N)\) memory is used for the array storing the temperature data, and the deques use at most \(O(K)\) memory.

Implementation Notes

• Store indices in the deque, not the values directly: To determine whether an element has gone out of the window’s range, it is common practice to store indices.

• Initialization: Until the window size reaches \(K\), only update the deques without computing the maximum and minimum values.

• Python’s collections.deque: When working with deques in Python, using collections.deque from the standard library allows \(O(1)\) operations on both the front and back.

  Source Code

import sys
from collections import deque

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    H = list(map(int, input_data[2:]))

    # スライディングウィンドウ内での最大値と最小値を管理するためのデック
    max_dq = deque()
    min_dq = deque()
    
    max_range = 0
    
    for i in range(N):
        # 最大値を管理するデックの更新
        while max_dq and H[max_dq[-1]] <= H[i]:
            max_dq.pop()
        max_dq.append(i)
        # ウィンドウの範囲外になった要素を削除
        if max_dq[0] <= i - K:
            max_dq.popleft()
            
        # 最小値を管理するデックの更新
        while min_dq and H[min_dq[-1]] >= H[i]:
            min_dq.pop()
        min_dq.append(i)
        # ウィンドウの範囲外になった要素を削除
        if min_dq[0] <= i - K:
            min_dq.popleft()
            
        # ウィンドウのサイズがKに達した時点から変動幅を計算
        if i >= K - 1:
            current_max = H[max_dq[0]]
            current_min = H[min_dq[0]]
            diff = current_max - current_min
            if diff > max_range:
                max_range = diff
                
    # 結果の出力
    print(max_range)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.