#cs/cp
# Count Subarrays With Cost Less Than or Equal to K (LC 3835)
## Problem Statement
We are given an integer array $nums=[n_0,\dots,n_{N-1}]$ and an integer $k$. Define the cost function
$
C(L, R) = \left(\max(n_L,\dots,n_R)-\min(n_L,\dots,n_R)\right)(R-L+1).
$
Find the number of subarrays whose cost is at most $k$.
## What Makes This Difficult?
1. Maintaining the minimum and maximum values of a dynamic window ([[Sliding Min or Max Window]]).
2. Recognizing that if $C(L,R)\leq k$, then $C(l,r)\leq k$ for every $L\leq l\leq r\leq R$. In a subarray of a valid window, both the range $\max-\min$ and the length can only decrease.
3. $C(i,i) = 0$.
## High-Level Idea
1. Create a sliding window of valid costs.
2. Create standard monotonic min and max deques that store indices for the current window.
3. Start at the beginning of the array with two pointers, $left$ and $right$.
4. Expand the window to the right.
1. If $C(left,right)\leq k$, count the valid subarrays ending at $right$.
2. If $C(left,right)>k$, move $left$ rightward until the window is valid again.
1. Once valid, count the subarrays ending at $right$.
5. Return the total count.
## Coded Solution
```python
from collections import deque
from typing import List
def countSubarrays(self, nums: List[int], k: int) -> int:
ans = left = 0
mn, mx = deque(), deque()
for right, x in enumerate(nums):
# Maintain the monotonic deques.
while mn and nums[mn[-1]] >= x:
mn.pop()
while mx and nums[mx[-1]] <= x:
mx.pop()
mn.append(right)
mx.append(right)
# Shrink the window while its cost is too large.
while (nums[mx[0]] - nums[mn[0]]) * (right - left + 1) > k:
# Remove an index when it leaves the window.
if mn[0] == left:
mn.popleft()
if mx[0] == left:
mx.popleft()
left += 1
ans += right - left + 1
return ans
```
The number of valid subarrays ending at `right` equals the current window length. Each index enters and leaves each deque at most once, so the algorithm runs in $O(N)$ time and uses $O(N)$ space in the worst case.