Overview

We want to find the length of the longest “contiguous subarray” such that the difference between the maximum and minimum temperatures within the interval is at most \(K\).
Since \(N\) can be up to \(2\times 10^5\), we need to efficiently manage the maximum and minimum of an interval.

Analysis

The condition for an interval \([l, r]\) (\(l \le r\)) to be stable is: $\(\max(A_l,\dots,A_r) - \min(A_l,\dots,A_r) \le K\)$

Why a naive approach is too slow

If we try all pairs \(l, r\), there are \(O(N^2)\) intervals, and computing the maximum and minimum for each takes \(O(N)\), leading to a worst case of \(O(N^3)\).
Even with precomputation, it is difficult to update “max/min of an arbitrary interval” each time, and a straightforward approach cannot improve beyond \(O(N^2)\) (which causes TLE for \(N=2\times 10^5\)).

Direction for the solution (key insight)

• By incrementing the right endpoint \(r\) one by one and “keeping the left endpoint \(l\) as small as possible while the condition is satisfied,” we can use the classic two-pointer technique (sliding window).
• However, at each step of the two-pointer method, we need to quickly know the “maximum and minimum values of the current interval.”
• By using a Monotonic Queue, each element is added and removed at most once, achieving an overall time complexity of \(O(N)\).

Algorithm

We move the interval \([l, r]\) using the two-pointer technique and manage the maximum and minimum within the interval using two deques:

• maxdq: A deque that stores candidate maximum values in decreasing order (monotonically decreasing)
  
  • When inserting a new value \(x\), pop from the back while the back element is smaller than \(x\) (since those elements are no longer needed)
    
  • The front maxdq[0] gives the current interval’s maximum value
• mindq: A deque that stores candidate minimum values in increasing order (monotonically increasing)
  
  • When inserting a new value \(x\), pop from the back while the back element is larger than \(x\)
    
  • The front mindq[0] gives the current interval’s minimum value

Procedure: 1. Move \(r\) from left to right, adding \(A_r\) to maxdq and mindq (removing unnecessary elements from the back to maintain monotonicity). 2. If maxdq[0] - mindq[0] > K, the condition is violated, so move the left endpoint \(l\) to the right to shrink the interval.
- When shrinking, if the value \(A_l\) leaving the interval matches the front of maxdq / mindq, popleft from the front (removing the max/min candidate that is now outside the interval).
- Repeat until the condition is satisfied. 3. Once the condition is satisfied, update the answer with the current interval length \(r-l+1\).

Small example

For \(A=[3,1,4,2],\ K=2\): - As \(r\) extends, the maximum and minimum change, but we can determine the difference just by looking at maxdq[0] and mindq[0] - If the difference exceeds \(2\), advance \(l\) to adjust
The strength of the monotonic queue is that this “extend, and shrink if invalid” operation runs in \(O(1)\) amortized time.

Complexity

• Time complexity: \(O(N)\)
  (Each element is added to maxdq/mindq at most once and removed at most once)
• Space complexity: \(O(N)\)
  (In the worst case, elements accumulate in the deques)

Implementation notes

• maxdq is maintained as monotonically decreasing by “popping while the back is smaller,” and mindq is maintained as monotonically increasing by “popping while the back is larger.”

• When moving the left endpoint, popleft() is called only when the value \(A_l\) leaving the interval matches the front of the deque (if it doesn’t match, that value is not at the front and has already been dropped as a candidate).

• In this implementation, the values themselves are stored in the deques. Even with duplicates, consistency is maintained by “only removing when equal to the front” (though a more general approach often stores indices instead).

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    maxdq = deque()  # decreasing
    mindq = deque()  # increasing

    l = 0
    ans = 0
    for r, x in enumerate(A):
        while maxdq and maxdq[-1] < x:
            maxdq.pop()
        maxdq.append(x)

        while mindq and mindq[-1] > x:
            mindq.pop()
        mindq.append(x)

        while maxdq[0] - mindq[0] > K:
            y = A[l]
            if maxdq[0] == y:
                maxdq.popleft()
            if mindq[0] == y:
                mindq.popleft()
            l += 1

        ans = max(ans, r - l + 1)

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.