2026-06-08：开销小于等于 K 的子数组数目。用go语言，给定整数数组 nums 和整数 k。 对数组中任意一个连续非空子数组 nums[l..r]，先找出该子数组的最大值 max 和最小值

2026-06-08：开销小于等于 K 的子数组数目。用go语言，给定整数数组 nums 和整数 k。
对数组中任意一个连续非空子数组 nums[l…r]，先找出该子数组的最大值 max 和最小值 min。然后用它们的差值乘以子数组长度 (r - l + 1)，得到该子数组的“代价”。

题目要求：统计 nums 里所有子数组中，代价不超过 k 的子数组一共有多少个，并返回这个数量。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

0 <= k <= 1000000000000000。

输入： nums = [1,3,2], k = 4。

输出： 5。

解释：

考虑 nums 的所有子数组：

nums[0…0]: cost = (1 - 1) * 1 = 0

nums[0…1]: cost = (3 - 1) * 2 = 4

nums[0…2]: cost = (3 - 1) * 3 = 6

nums[1…1]: cost = (3 - 3) * 1 = 0

nums[1…2]: cost = (3 - 2) * 2 = 2

nums[2…2]: cost = (2 - 2) * 1 = 0

共有 5 个子数组的开销小于或等于 4。

题目来自力扣3835。

逐步骤详细执行过程

初始状态：

• 左指针left = 0
• 最小队列minQ空，最大队列maxQ空
• 答案ans = 0
• 数组：[1, 3, 2]，索引0、1、2

第一步：遍历右边界 right = 0，元素值 = 1

1. 元素入队（维护两个单调队列）

• 最小队列：空，直接把下标0加入 →minQ = [0]（队首是当前最小值）
• 最大队列：空，直接把下标0加入 →maxQ = [0]（队首是当前最大值）

2. 检查窗口是否合法（代价 ≤k）

当前窗口[0,0]：
最大值=1，最小值=1，差值=0
长度=1
代价=0×1=0 ≤4 → 窗口合法，不移动左指针

3. 统计合法子数组数量

以right=0结尾的合法子数组：只有[0,0]
答案累加：ans = 0 + 1 = 1

第二步：遍历右边界 right = 1，元素值 = 3

1. 元素入队（维护两个单调队列）

• 最小队列：当前元素3 ≥ 队尾下标0对应的值1，不破坏单调递增，直接加入 →minQ = [0,1]
• 最大队列：当前元素3 ≥ 队尾下标0对应的值1，需要弹出队尾，队列变空后加入 →maxQ = [1]

2. 检查窗口是否合法

当前窗口[0,1]：
最大值=3（队首1），最小值=1（队首0），差值=2
长度=2
代价=2×2=4 ≤4 → 窗口合法，不移动左指针

3. 统计合法子数组数量

以right=1结尾的合法子数组：[0,1]、[1,1]→ 共2个
答案累加：ans = 1 + 2 = 3

第三步：遍历右边界 right = 2，元素值 = 2

1. 元素入队（维护两个单调队列）

• 最小队列：当前元素2 ≤ 队尾下标1对应的值3，弹出队尾；队列变为[0]，2 ≥ 下标0对应的值1，加入 →minQ = [0,2]
• 最大队列：当前元素2 ≤ 队尾下标1对应的值3，不破坏单调递减，直接加入 →maxQ = [1,2]

2. 检查窗口是否合法（关键：窗口不合法，移动左指针）

当前窗口[0,2]：
最大值=3（队首1），最小值=1（队首0），差值=2
长度=3
代价=2×3=6 >4 →窗口不合法

• 左指针右移：left = 1
• 检查最小队列：队首0 < left=1，弹出 →minQ = [2]
• 检查最大队列：队首1 ≥ left=1，保留

现在窗口[1,2]：
最大值=3（队首1），最小值=2（队首2），差值=1
长度=2
代价=1×2=2 ≤4 → 窗口合法，停止移动左指针

3. 统计合法子数组数量

以right=2结尾的合法子数组：[1,2]、[2,2]→ 共2个
答案累加：ans = 3 + 2 = 5

遍历结束

最终总答案 = 5，和题目输出完全一致。

时间复杂度 & 额外空间复杂度

1. 总时间复杂度：O(n)

• 滑动窗口：左右指针left和right只会向右移动，绝不回退，总共最多移动2n次；
• 单调队列：每个数组元素只会入队一次、出队一次，没有重复操作；
• 所有操作都是线性的，与数组长度n成正比。

2. 总额外空间复杂度：O(n)

• 额外使用了两个单调队列存储数组下标；
• 最坏情况下（数组严格递增/递减），队列会存储全部n个元素；
• 除了输入输出和变量，仅占用线性级别的额外空间。

总结

1. 执行过程：逐一遍历右边界→维护双队列获取窗口最值→检查窗口合法性→移动左指针→统计合法子数组数量并累加；
2. 时间复杂度：O(n)（线性时间，适合10万长度的数组）；
3. 额外空间复杂度：O(n)（两个单调队列的最大存储量）。

Go完整代码如下：

packagemainimport("fmt")funccountSubarrays(nums[]int,kint64)(ansint64){varminQ,maxQ[]intleft:=0forright,x:=rangenums{// 1. 入：元素进入窗口forlen(minQ)>0&&x<=nums[minQ[len(minQ)-1]]{minQ=minQ[:len(minQ)-1]}minQ=append(minQ,right)forlen(maxQ)>0&&x>=nums[maxQ[len(maxQ)-1]]{maxQ=maxQ[:len(maxQ)-1]}maxQ=append(maxQ,right)// 2. 出：如果窗口不满足要求，左端点离开窗口// 只需改下面这行代码，其余逻辑和 2762 题完全一致forint64(nums[maxQ[0]]-nums[minQ[0]])*int64(right-left+1)>k{left++ifminQ[0]<left{minQ=minQ[1:]}ifmaxQ[0]<left{maxQ=maxQ[1:]}}// 3. 更新答案ans+=int64(right-left+1)}return}funcmain(){nums:=[]int{1,3,2}k:=4result:=countSubarrays(nums,int64(k))fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromcollectionsimportdequedefcountSubarrays(nums,k):ans=0minQ=deque()maxQ=deque()left=0forright,xinenumerate(nums):# 1. 入：元素进入窗口whileminQandx<=nums[minQ[-1]]:minQ.pop()minQ.append(right)whilemaxQandx>=nums[maxQ[-1]]:maxQ.pop()maxQ.append(right)# 2. 出：如果窗口不满足要求，左端点离开窗口whilemaxQandminQand(nums[maxQ[0]]-nums[minQ[0]])*(right-left+1)>k:left+=1ifminQandminQ[0]<left:minQ.popleft()ifmaxQandmaxQ[0]<left:maxQ.popleft()# 3. 更新答案ans+=right-left+1returnansdefmain():nums=[1,3,2]k=4result=countSubarrays(nums,k)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<deque>usingnamespacestd;longlongcountSubarrays(vector<int>&nums,longlongk){longlongans=0;deque<int>minQ,maxQ;intleft=0;for(intright=0;right<nums.size();right++){intx=nums[right];// 1. 入：元素进入窗口while(!minQ.empty()&&x<=nums[minQ.back()]){minQ.pop_back();}minQ.push_back(right);while(!maxQ.empty()&&x>=nums[maxQ.back()]){maxQ.pop_back();}maxQ.push_back(right);// 2. 出：如果窗口不满足要求，左端点离开窗口while(!minQ.empty()&&!maxQ.empty()&&(longlong)(nums[maxQ.front()]-nums[minQ.front()])*(right-left+1)>k){left++;if(!minQ.empty()&&minQ.front()<left){minQ.pop_front();}if(!maxQ.empty()&&maxQ.front()<left){maxQ.pop_front();}}// 3. 更新答案ans+=(right-left+1);}returnans;}intmain(){vector<int>nums={1,3,2};longlongk=4;longlongresult=countSubarrays(nums,k);cout<<result<<endl;return0;}