Overview

For each contiguous subarray of length \(K\), compute “maximum − minimum” and find the overall maximum. The key point is efficiently updating the maximum and minimum for each window.

Analysis

The fluctuation range over each \(K\)-day period can be expressed as \(\max - \min\) using the highest temperature \(\max\) and lowest temperature \(\min\) within that interval. Therefore, the problem reduces to “finding \(\max\) and \(\min\) for every subarray of length \(K\), and taking the maximum of their differences.”

A naive approach would require, for each interval \([l, l+K-1]\): - \(O(K)\) to find the maximum - \(O(K)\) to find the minimum

Since there are \(N-K+1\) intervals, the total complexity is \(O(NK)\). Given that \(N \le 2\times 10^5\) and \(K\) can be of similar magnitude, this is too slow.

Instead of recomputing the maximum and minimum from scratch for each “sliding window,” we update the information as the window advances by one day, allowing retrieval in amortized \(O(1)\).

Algorithm

We use two monotonic queues (Monotonic Queue).

• Max deque maxdq: Maintains indices such that the temperatures are monotonically decreasing from front to back.

  • When inserting a new value \(x = H_i\), remove elements from the back where \(H[\text{back}] \le x\) (since they can never be the maximum in the future), then append \(i\).
  • The front always holds the “index of the maximum value in the current window.”

• Min deque mindq: Maintains indices such that the temperatures are monotonically increasing from front to back.

  • When inserting a new value \(x\), remove elements from the back where \(H[\text{back}] \ge x\) (since they can never be the minimum in the future), then append \(i\).
  • The front always holds the “index of the minimum value in the current window.”

Let the left endpoint of the window be \(left = i - K + 1\). When \(left \ge 0\), a complete window of length \(K\) has been formed. At that point: - If the front index is outside the window (\(< left\)), remove it from the front (popleft). - The maximum is H[maxdq[0]]. - The minimum is H[mindq[0]]. - Update the answer with the difference diff = H[maxdq[0]] - H[mindq[0]].

Concrete Example

Consider \(H=[3,1,4,1,5],\ K=3\). The windows are: - \([3,1,4]\): \(\max=4,\min=1,\ diff=3\) - \([1,4,1]\): \(\max=4,\min=1,\ diff=3\) - \([4,1,5]\): \(\max=5,\min=1,\ diff=4\)

The maximum is 4. Using monotonic queues, we can retrieve \(\max\) and \(\min\) for each window without scanning through it every time.

Complexity

• Time complexity: \(O(N)\) Each element enters the deque at most once and leaves at most once, so the total work is linear (amortized \(O(1)\)).
• Space complexity: \(O(K)\) (at most \(O(N)\)) The deques store indices near the window, and each deque has length at most around \(K\).

Implementation Notes

• Storing indices rather than values in the deques makes it easy to check whether an element has fallen outside the window (\(< left\)).

• For the max deque, the removal condition is “back value \(\le\) new value”; for the min deque, it is “back value \(\ge\) new value” — the comparison directions are opposite.

• The window is complete only when \(i \ge K-1\) (i.e., \(left \ge 0\)), so compute the difference only at those times.

• Temperatures can be negative, but the difference \(\max - \min\) is always \(\ge 0\), so initializing with ans = 0 is fine.

  Source Code

import sys
from collections import deque

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

    maxdq = deque()  # indices, H values decreasing
    mindq = deque()  # indices, H values increasing

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

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

        left = i - K + 1
        if left >= 0:
            while maxdq[0] < left:
                maxdq.popleft()
            while mindq[0] < left:
                mindq.popleft()
            diff = H[maxdq[0]] - H[mindq[0]]
            if diff > ans:
                ans = diff

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.