Variable Window Max Min

When To Use

Use this when a variable-size window is valid based on the current max and min.

Prerequisite: Base Monotonic Deque

Template

for r = 0; r < n; r++:
    push r into max_dq
    push r into min_dq
 
    while max - min is invalid:
        remove l from both deques if present
        l++
 
    update answer

Variable window means the left boundary is explicit and condition-driven.

Problems

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Problem: longest window where max - min <= limit.

Pattern: maintain both extrema while moving l.

Applied pseudocode:

for r = 0; r < n; r++:
    while max_dq not empty and nums[max_dq.back] <= nums[r]:
        max_dq.pop_back()
    max_dq.push_back(r)
 
    while min_dq not empty and nums[min_dq.back] >= nums[r]:
        min_dq.pop_back()
    min_dq.push_back(r)
 
    while nums[max_dq.front] - nums[min_dq.front] > limit:
        if max_dq.front == l:
            max_dq.pop_front()
        if min_dq.front == l:
            min_dq.pop_front()
        l++
 
    ans = max(ans, r - l + 1)

Continuous Subarrays

Problem: count subarrays where max - min <= 2.

Pattern: same boundary as above, but add r - l + 1.

Count Partitions With Max-Min Difference At Most K

Problem: count ways to partition so every part has max - min <= k.

Pattern: same left boundary, then DP with prefix sums.

Count Prime Gap Balanced Subarrays

Problem: count subarrays where prime max and prime min differ by at most k.

Pattern: extrema deques only track prime indices.

Maximum Number of Robots Within Budget

Problem: longest window where max(charge) + len * sum(running) <= budget.

Pattern: max deque plus running-cost prefix sum.