Continuous Subarrays

"""
QUESTION
--------
Given an array `nums`, a subarray is "continuous" if for every pair of its
elements the absolute difference is at most 2 (equivalently max - min <= 2).
Return the total number of continuous subarrays.

EXAMPLES
--------
continuous_subarrays([5, 4, 2, 4]) -> 8
continuous_subarrays([1, 2, 3])    -> 6

HINT (two monotonic queues = a sliding window)
----------------------------------------------
Grow a window with right pointer; keep a max-deque and a min-deque of the
current window. While  max - min > 2,  advance left (popping from whichever
deque's front falls out). For each right, all subarrays ending at right and
starting in [left, right] are valid -> add (right - left + 1).
O(n).
"""
from collections import deque


def continuous_subarrays(nums):
    min_dq = deque()
    max_dq = deque()
    left = 0
    total = 0

    for right, x in enumerate(nums):
        while min_dq and nums[min_dq[-1]] >= x:
            min_dq.pop()
        min_dq.append(right)

        while max_dq and nums[max_dq[-1]] <= x:
            max_dq.pop()
        max_dq.append(right)

        while nums[max_dq[0]] - nums[min_dq[0]] > 2:
            left += 1
            if min_dq[0] < left:
                min_dq.popleft()
            if max_dq[0] < left:
                max_dq.popleft()

        total += right - left + 1

    return total


assert continuous_subarrays([5, 4, 2, 4]) == 8
assert continuous_subarrays([1, 2, 3]) == 6
assert continuous_subarrays([1, 1, 1]) == 6
assert continuous_subarrays([31, 25, 72, 79, 74]) == 5