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 0nums[0…1]: cost (3 - 1) * 2 4nums[0…2]: cost (3 - 1) * 3 6nums[1…1]: cost (3 - 3) * 1 0nums[1…2]: cost (3 - 2) * 2 2nums[2…2]: cost (2 - 2) * 1 0共有 5 个子数组的开销小于或等于 4。题目来自力扣3835。逐步骤详细执行过程初始状态左指针left 0最小队列minQ空最大队列maxQ空答案ans 0数组[1, 3, 2]索引0、1、2第一步遍历右边界 right 0元素值 11. 元素入队维护两个单调队列最小队列空直接把下标0加入 →minQ [0]队首是当前最小值最大队列空直接把下标0加入 →maxQ [0]队首是当前最大值2. 检查窗口是否合法代价 ≤k当前窗口[0,0]最大值1最小值1差值0长度1代价0×10 ≤4 → 窗口合法不移动左指针3. 统计合法子数组数量以right0结尾的合法子数组只有[0,0]答案累加ans 0 1 1第二步遍历右边界 right 1元素值 31. 元素入队维护两个单调队列最小队列当前元素3 ≥ 队尾下标0对应的值1不破坏单调递增直接加入 →minQ [0,1]最大队列当前元素3 ≥ 队尾下标0对应的值1需要弹出队尾队列变空后加入 →maxQ [1]2. 检查窗口是否合法当前窗口[0,1]最大值3队首1最小值1队首0差值2长度2代价2×24 ≤4 → 窗口合法不移动左指针3. 统计合法子数组数量以right1结尾的合法子数组[0,1]、[1,1]→ 共2个答案累加ans 1 2 3第三步遍历右边界 right 2元素值 21. 元素入队维护两个单调队列最小队列当前元素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×36 4 →窗口不合法左指针右移left 1检查最小队列队首0 left1弹出 →minQ [2]检查最大队列队首1 ≥ left1保留现在窗口[1,2]最大值3队首1最小值2队首2差值1长度2代价1×22 ≤4 → 窗口合法停止移动左指针3. 统计合法子数组数量以right2结尾的合法子数组[1,2]、[2,2]→ 共2个答案累加ans 3 2 5遍历结束最终总答案 5和题目输出完全一致。时间复杂度 额外空间复杂度1. 总时间复杂度O(n)滑动窗口左右指针left和right只会向右移动绝不回退总共最多移动2n次单调队列每个数组元素只会入队一次、出队一次没有重复操作所有操作都是线性的与数组长度n成正比。2. 总额外空间复杂度O(n)额外使用了两个单调队列存储数组下标最坏情况下数组严格递增/递减队列会存储全部n个元素除了输入输出和变量仅占用线性级别的额外空间。总结执行过程逐一遍历右边界→维护双队列获取窗口最值→检查窗口合法性→移动左指针→统计合法子数组数量并累加时间复杂度O(n)线性时间适合10万长度的数组额外空间复杂度O(n)两个单调队列的最大存储量。Go完整代码如下packagemainimport(fmt)funccountSubarrays(nums[]int,kint64)(ansint64){varminQ,maxQ[]intleft:0forright,x:rangenums{// 1. 入元素进入窗口forlen(minQ)0xnums[minQ[len(minQ)-1]]{minQminQ[:len(minQ)-1]}minQappend(minQ,right)forlen(maxQ)0xnums[maxQ[len(maxQ)-1]]{maxQmaxQ[:len(maxQ)-1]}maxQappend(maxQ,right)// 2. 出如果窗口不满足要求左端点离开窗口// 只需改下面这行代码其余逻辑和 2762 题完全一致forint64(nums[maxQ[0]]-nums[minQ[0]])*int64(right-left1)k{leftifminQ[0]left{minQminQ[1:]}ifmaxQ[0]left{maxQmaxQ[1:]}}// 3. 更新答案ansint64(right-left1)}return}funcmain(){nums:[]int{1,3,2}k:4result:countSubarrays(nums,int64(k))fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromcollectionsimportdequedefcountSubarrays(nums,k):ans0minQdeque()maxQdeque()left0forright,xinenumerate(nums):# 1. 入元素进入窗口whileminQandxnums[minQ[-1]]:minQ.pop()minQ.append(right)whilemaxQandxnums[maxQ[-1]]:maxQ.pop()maxQ.append(right)# 2. 出如果窗口不满足要求左端点离开窗口whilemaxQandminQand(nums[maxQ[0]]-nums[minQ[0]])*(right-left1)k:left1ifminQandminQ[0]left:minQ.popleft()ifmaxQandmaxQ[0]left:maxQ.popleft()# 3. 更新答案ansright-left1returnansdefmain():nums[1,3,2]k4resultcountSubarrays(nums,k)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includedequeusingnamespacestd;longlongcountSubarrays(vectorintnums,longlongk){longlongans0;dequeintminQ,maxQ;intleft0;for(intright0;rightnums.size();right){intxnums[right];// 1. 入元素进入窗口while(!minQ.empty()xnums[minQ.back()]){minQ.pop_back();}minQ.push_back(right);while(!maxQ.empty()xnums[maxQ.back()]){maxQ.pop_back();}maxQ.push_back(right);// 2. 出如果窗口不满足要求左端点离开窗口while(!minQ.empty()!maxQ.empty()(longlong)(nums[maxQ.front()]-nums[minQ.front()])*(right-left1)k){left;if(!minQ.empty()minQ.front()left){minQ.pop_front();}if(!maxQ.empty()maxQ.front()left){maxQ.pop_front();}}// 3. 更新答案ans(right-left1);}returnans;}intmain(){vectorintnums{1,3,2};longlongk4;longlongresultcountSubarrays(nums,k);coutresultendl;return0;}