1class Solution {
2    public long countSubarrays(int[] nums, long k) {
3        long answer = 0;
4
5        // Monotonic decreasing deque: stores indices whose values are in
6        // decreasing order, so the front always holds the index of the
7        // maximum value in the current window.
8        Deque<Integer> maxDeque = new ArrayDeque<>();
9
10        // Monotonic increasing deque: stores indices whose values are in
11        // increasing order, so the front always holds the index of the
12        // minimum value in the current window.
13        Deque<Integer> minDeque = new ArrayDeque<>();
14
15        // Left boundary of the sliding window.
16        int left = 0;
17
18        // Right boundary of the sliding window; iterate over each element.
19        for (int right = 0; right < nums.length; right++) {
20            int current = nums[right];
21
22            // Maintain the decreasing order in maxDeque: remove all indices
23            // from the back whose values are less than or equal to current.
24            while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= current) {
25                maxDeque.pollLast();
26            }
27
28            // Maintain the increasing order in minDeque: remove all indices
29            // from the back whose values are greater than or equal to current.
30            while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= current) {
31                minDeque.pollLast();
32            }
33
34            // Add the current index to both deques.
35            maxDeque.addLast(right);
36            minDeque.addLast(right);
37
38            // Shrink the window from the left while the score of the window
39            // exceeds k. The score is defined as:
40            //   (max value - min value) * (window length)
41            while (left < right
42                    && (long) (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()])
43                            * (right - left + 1) > k) {
44                left++;
45                // If the front index of maxDeque is now outside the window,
46                // remove it.
47                if (maxDeque.peekFirst() < left) {
48                    maxDeque.pollFirst();
49                }
50                // If the front index of minDeque is now outside the window,
51                // remove it.
52                if (minDeque.peekFirst() < left) {
53                    minDeque.pollFirst();
54                }
55            }
56
57            // All subarrays ending at "right" with start index in [left, right]
58            // satisfy the constraint, so add their count.
59            answer += right - left + 1;
60        }
61
62        return answer;
63    }
64}
65

1class Solution {
2public:
3    long long countSubarrays(vector<int>& nums, long long k) {
4        long long answer = 0;
5
6        // maxDeque: indices of candidates for the window maximum,
7        //           values are kept in non-increasing order (front = max).
8        // minDeque: indices of candidates for the window minimum,
9        //           values are kept in non-decreasing order (front = min).
10        deque<int> maxDeque, minDeque;
11
12        int left = 0;
13        int n = static_cast<int>(nums.size());
14
15        for (int right = 0; right < n; right++) {
16            int current = nums[right];
17
18            // Maintain a monotonically non-increasing deque for the maximum.
19            // Pop smaller-or-equal elements from the back since they can never
20            // be the maximum while the newer, larger element is in the window.
21            while (!maxDeque.empty() && nums[maxDeque.back()] <= current) {
22                maxDeque.pop_back();
23            }
24
25            // Maintain a monotonically non-decreasing deque for the minimum.
26            // Pop larger-or-equal elements from the back for the same reason.
27            while (!minDeque.empty() && nums[minDeque.back()] >= current) {
28                minDeque.pop_back();
29            }
30
31            maxDeque.push_back(right);
32            minDeque.push_back(right);
33
34            // Shrink the window from the left while the score
35            // (max - min) * length exceeds k.
36            while (left < right &&
37                   static_cast<long long>(nums[maxDeque.front()] - nums[minDeque.front()]) *
38                           (right - left + 1) > k) {
39                left++;
40
41                // Remove indices that have fallen out of the window [left, right].
42                if (maxDeque.front() < left) {
43                    maxDeque.pop_front();
44                }
45                if (minDeque.front() < left) {
46                    minDeque.pop_front();
47                }
48            }
49
50            // Every subarray ending at 'right' with start in [left, right]
51            // is valid, contributing (right - left + 1) subarrays.
52            answer += right - left + 1;
53        }
54
55        return answer;
56    }
57};
58

1/**
2 * Counts the number of subarrays where (max - min) * length <= k.
3 * Uses two monotonic deques to track the maximum and minimum values
4 * within the current sliding window.
5 *
6 * @param nums - The input array of numbers.
7 * @param k - The threshold value for the condition.
8 * @returns The total count of valid subarrays.
9 */
10function countSubarrays(nums: number[], k: number): number {
11    // Accumulates the total number of valid subarrays.
12    let answer = 0;
13
14    // Monotonic decreasing deque storing indices; front holds the window's maximum.
15    const maxDeque: number[] = [];
16    // Monotonic increasing deque storing indices; front holds the window's minimum.
17    const minDeque: number[] = [];
18
19    // Head and tail pointers for the max deque (simulating a deque via array indices).
20    let maxHead = 0;
21    let maxTail = 0;
22    // Head and tail pointers for the min deque.
23    let minHead = 0;
24    let minTail = 0;
25
26    // Left boundary of the sliding window.
27    let left = 0;
28
29    // Expand the window by moving the right boundary one step at a time.
30    for (let right = 0; right < nums.length; right++) {
31        const value = nums[right];
32
33        // Maintain the max deque as monotonically decreasing:
34        // pop indices whose values are not greater than the incoming value.
35        while (maxHead < maxTail && nums[maxDeque[maxTail - 1]] <= value) {
36            maxTail--;
37        }
38        // Maintain the min deque as monotonically increasing:
39        // pop indices whose values are not less than the incoming value.
40        while (minHead < minTail && nums[minDeque[minTail - 1]] >= value) {
41            minTail--;
42        }
43
44        // Push the current index into both deques.
45        maxDeque[maxTail++] = right;
46        minDeque[minTail++] = right;
47
48        // Shrink the window from the left while the condition is violated:
49        // (currentMax - currentMin) * windowLength > k.
50        while (
51            left < right &&
52            (nums[maxDeque[maxHead]] - nums[minDeque[minHead]]) * (right - left + 1) > k
53        ) {
54            left++;
55            // Discard deque fronts that fall outside the new window.
56            if (maxDeque[maxHead] < left) {
57                maxHead++;
58            }
59            if (minDeque[minHead] < left) {
60                minHead++;
61            }
62        }
63
64        // Every subarray ending at 'right' with start index in [left, right] is valid.
65        answer += right - left + 1;
66    }
67
68    return answer;
69}
70