Overview

This problem asks us to find the maximum length of a contiguous subarray that is “mountain-shaped” and where the difference between the maximum and minimum values in the subarray is at least \(K\).

Analysis

In this problem, we need to efficiently find intervals that satisfy the conditions. Since \(N\) can be up to \(10^6\), an \(O(N^2)\) approach that checks all intervals will not pass within the time limit. Therefore, we need to solve it in \(O(N)\) or \(O(N \log N)\) time.

First, let’s focus on the “mountain-shaped” intervals. A mountain-shaped interval has a peak \(k\), and is strictly decreasing to the left and strictly decreasing to the right. If we fix a vertex \(k\) as the peak of the mountain, we can think about expanding this mountain-shaped interval as far as possible to the left and right. The left side can be expanded as long as \(H_i < H_{i+1}\) holds, and the right side can be expanded as long as \(H_i > H_{i+1}\) holds. By precomputing this, we can find the widest mountain-shaped interval for each \(k\) in \(O(1)\) time.

Next, let’s consider the condition “the difference between the maximum and minimum values is at least \(K\)”. Let \([l, r]\) be the widest mountain-shaped interval corresponding to peak \(k\). In this case, the maximum value in the interval is the peak’s height \(H_k\). Now, let’s consider the minimum value. Since the height decreases as we move further left on the left side, and decreases as we move further right on the right side, the minimum value in the interval must be either the height of the left end \(H_l\) or the height of the right end \(H_r\), whichever is smaller. Thus, the difference between the maximum and minimum values in the interval is \(H_k - \min(H_l, H_r)\). The condition for this difference to be at least \(K\) can be written as \(H_l \leq H_k - K\) or \(H_r \leq H_k - K\).

If a mountain-shaped interval with peak \(k\) satisfies the condition, it is sufficient to check whether the widest interval \([l, r]\) satisfies the condition. This is because shrinking the interval will either keep the maximum value the same or decrease it, and will increase the minimum value, thereby only decreasing the difference and making it harder to satisfy the condition of being at least \(K\). Therefore, we can find the overall longest interval simply by computing the widest mountain-shaped interval for every peak \(k\) and checking if it satisfies the condition.

Algorithm

1. Compute the array L[i]. L[i] is the maximum length of a strictly increasing contiguous subarray ending at index \(i\). From left to right, if \(H_{i-1} < H_i\), then L[i] = L[i-1] + 1, otherwise 1.
2. Compute the array R[i]. R[i] is the maximum length of a strictly decreasing contiguous subarray starting at index \(i\). From right to left, if \(H_i > H_{i+1}\), then R[i] = R[i+1] + 1, otherwise 1.
3. Assuming each \(i\) is the peak of a mountain, find the left end li = i - L[i] + 1 and the right end ri = i + R[i] - 1 of the widest mountain-shaped interval.
4. The minimum value in the interval is \(\min(H[li], H[ri])\). If the condition \(H[li] \leq H[i] - K\) or \(H[ri] \leq H[i] - K\) is satisfied, update the maximum length using the interval length L[i] + R[i] - 1 as a candidate.
5. After checking all \(i\), output the maximum length.

Complexity

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

Implementation Points

• The key to solving this problem in linear time is realizing that “the minimum value in the interval is either at the left end or the right end”. Due to the properties of a mountain shape, the height decreases as you get closer to the ends, so there is no need to use a Segment Tree or similar data structures to find the range minimum.

• In slower languages like Python, you should use sys.stdin.readline to read the input to reduce input overhead and ensure it passes within the time limit.

  Source Code

import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    L = [1] * N
    for i in range(1, N):
        if H[i-1] < H[i]:
            L[i] = L[i-1] + 1
            
    R = [1] * N
    for i in range(N-2, -1, -1):
        if H[i] > H[i+1]:
            R[i] = R[i+1] + 1
            
    ans = 0
    for i in range(N):
        li = i - L[i] + 1
        ri = i + R[i] - 1
        if H[li] <= H[i] - K or H[ri] <= H[i] - K:
            length = L[i] + R[i] - 1
            if length > ans:
                ans = length
                
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by or-glm5.2-high.