Overview

This problem asks you to find the interval within consecutive \(K\) days of temperature data where the difference between the maximum and minimum temperatures (the variation range) is maximized. We solve this efficiently by combining a sliding window with monotonic queues.

Analysis

Naive Approach and Its Issues

The simplest method is to find the maximum and minimum values for every consecutive \(K\)-day interval.

• There are \(N - K + 1\) intervals of consecutive \(K\) days in total
• Finding the maximum and minimum for each interval takes \(O(K)\)
• Total: \(O((N-K+1) \times K) = O(NK)\)

When \(N = 2 \times 10^5\), this results in approximately \(10^{10}\) operations in the worst case, causing TLE (Time Limit Exceeded).

Key Insight

When sliding the window by one position, only one element is added and one element is removed. By exploiting this property, we don’t need to re-examine all elements every time.

Solution: Monotonic Deque

A monotonic deque is a data structure that can retrieve the maximum and minimum values within a sliding window in \(O(1)\) (amortized) time.

Example of how the maximum value queue (descending order) works: For array [3, 1, 4, 1, 5] with \(K = 3\)

Step	Added Element	Queue State (indices)	Window Maximum
i=0	3	[0]	-
i=1	1	[0, 1]	-
i=2	4	2	4
i=3	1	[2, 3]	4
i=4	5	4	5

Algorithm

1. Prepare two monotonic queues

   • max_deque: Manages the maximum value (maintained in descending order)
   • min_deque: Manages the minimum value (maintained in ascending order)

2. Process each element in order

   • When adding a new element, remove unnecessary elements from the back of the queue
     • max_deque: Remove elements less than or equal to the new element
     • min_deque: Remove elements greater than or equal to the new element
   • Add the index to the queue

3. When the window size reaches \(K\)

   • Remove from the front if the queue’s front is outside the window
   • max_deque[0] is the index of the maximum value, min_deque[0] is the index of the minimum value
   • Calculate variation = maximum - minimum and update the answer

Complexity

• Time Complexity: \(O(N)\)

  • Each element is added to the queue at most once and removed at most once
  • Total of \(O(N)\) operations

• Space Complexity: \(O(K)\)

  • Each queue contains at most \(K\) elements

Implementation Notes

1. Store indices

   • Store indices rather than values in the queues. This allows us to determine whether an element is within the window.

2. Timing for removing elements outside the window

   • Remove from the front of the queue when it’s outside the window (index < i - K + 1).

3. Handling equality

   • In max_deque, remove with <= (keep the newer one when values are equal)
   • In min_deque, remove with >= (keep the newer one when values are equal)
   • This ensures correct behavior even when there are multiple identical values.

Source Code

from collections import deque

def solve():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    # Efficiently manage maximum and minimum values with sliding window
    # Using Monotonic Deque
    
    max_deque = deque()  # Manages maximum value (descending order)
    min_deque = deque()  # Manages minimum value (ascending order)
    
    max_variation = 0
    
    for i in range(N):
        # Add new element
        # max_deque: Remove elements smaller than current element from the back
        while max_deque and H[max_deque[-1]] <= H[i]:
            max_deque.pop()
        max_deque.append(i)
        
        # min_deque: Remove elements larger than current element from the back
        while min_deque and H[min_deque[-1]] >= H[i]:
            min_deque.pop()
        min_deque.append(i)
        
        # When window size becomes K
        if i >= K - 1:
            # Remove elements outside the window from the front
            while max_deque[0] < i - K + 1:
                max_deque.popleft()
            while min_deque[0] < i - K + 1:
                min_deque.popleft()
            
            # Calculate variation of current window
            current_max = H[max_deque[0]]
            current_min = H[min_deque[0]]
            variation = current_max - current_min
            
            max_variation = max(max_variation, variation)
    
    print(max_variation)

solve()

---

This editorial was generated by claude4.5opus.