2026-06-08：开销小于等于 K 的子数组数目。用go语言，给定整数数组 nums 和整数 k。 对数组中任意一个连续非空子数组 nums[l…..

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完整代码如下：

package main

 import (
    "fmt"
)

 func countSubarrays(nums []int, k int64) (ans int64) {
    var minQ, maxQ []int
    left := 0
    for right, x := range nums {
        // 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++
            if minQ[0] < left {
                minQ = minQ[1:]
            }
            if maxQ[0] < left {
                maxQ = maxQ[1:]
            }
        }

         // 3. 更新答案
        ans += int64(right - left + 1)
    }
    return
}

 func main() {
    nums := []int{1, 3, 2}
    k := 4
    result := countSubarrays(nums, int64(k))
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from collections import deque

 def countSubarrays(nums, k):
    ans = 0
    minQ = deque()
    maxQ = deque()
    left = 0
    for right, x in enumerate(nums):
        # 1. 入：元素进入窗口
        while minQ and x <= nums[minQ[-1]]:
            minQ.pop()
        minQ.append(right)
        while maxQ and x >= nums[maxQ[-1]]:
            maxQ.pop()
        maxQ.append(right)
        # 2. 出：如果窗口不满足要求，左端点离开窗口
        while maxQ and minQ and (nums[maxQ[0]] - nums[minQ[0]]) * (right - left + 1) > k:
            left += 1
            if minQ and minQ[0] < left:
                minQ.popleft()
            if maxQ and maxQ[0] < left:
                maxQ.popleft()
        # 3. 更新答案
        ans += right - left + 1
    return ans

 def main():
    nums = [1, 3, 2]
    k = 4
    result = countSubarrays(nums, k)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  

  

  


 using namespace std;

 long long countSubarrays(vector& nums, long long k) {
    long long ans = 0;
    deque minQ, maxQ;
    int left = 0;

     for (int right = 0; right < nums.size(); right++) {
        int x = 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() &&
               (long long)(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);
    }

     return ans;
}

 int main() {
    vector nums = {1, 3, 2};
    long long k = 4;
    long long result = countSubarrays(nums, k);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。