区间子数组个数：巧用计数函数实现O(n)复杂度解法

刚看到一个帖子，讲的是职场面试里的一个真实故事。一位90年的候选人去应聘经理岗，张口期望薪资是40k以上，面试前半段聊得都挺顺畅的。结果HR总监突然来了个“灵魂发问”：“你这年纪选择主动离职，够有勇气的啊。”候选人只能苦笑回应，说原公司已经六个月没发工资了，不离职难道等着喝西北风吗？

网上评论五花八门，有人说候选人要价太高，也有人反驳说拖欠工资就别谈忠诚。这事儿其实可以分开看：半年没薪水，离职不是“勇气”，而是基本生存逻辑；至于40k贵不贵，关键看能力、岗位和市场行情，跟年龄或是否“听话”关系不大。真正值得讨论的，是那些拖欠薪资却还幻想员工无私奉献的公司。

站在程序员的角度，咱们都知道职场里不该被“稳定”和“忠诚”这类话术束缚。公司可以计算成本，打工人同样有权维护自己的现金流和职业发展。在面对类似情况时，合理的薪资谈判技巧和清晰的职业规划就显得尤为重要。

好了，闲聊到此为止，下面进入咱们今天的正题——一道经典又有趣的算法题。

算法题：区间子数组个数

给定一个整数数组 nums，以及两个整数 left 和 right。要求统计出：有多少个连续子数组，其子数组内的最大值恰好落在 [left, right] 这个闭区间内。

举个简单的例子：

nums = [2, 1, 4, 3]
left, right = 2, 3

符合要求的子数组有三个：

• [2]，最大值2在区间内
• [2, 1]，最大值2在区间内
• [3]，最大值3在区间内

所以最终答案是 3。

题目听起来不难，对吧？但如果你直接使用暴力枚举，在数据量较大时（比如数组长度达到 1e5 级别）很容易超时。我们先来看看最直接的思路：

1. 枚举所有子数组（使用双层循环，i 为左边界，j 为右边界）
2. 遍历每个子数组时，计算其最大值
3. 判断该最大值是否在 [left, right] 区间内，是则计数器加一

伪代码大概是这个样子：

ans = 0
for i in range(n):
    cur_max = nums[i]
    for j in range(i, n):
        cur_max = max(cur_max, nums[j])
        if left <= cur_max <= right:
            ans += 1

问题很明显：如果数组长度为 n，这个算法的时间复杂度是 O(n²)，当 n 很大时必然“超时”。

那么，如何才能将其优化到 O(n) 复杂度呢？这道题其实有一个非常巧妙的小套路。

关键观察：先计算“最大值 ≤ 某个值”的子数组

我们不要死盯着 [left, right] 这个区间，试着把问题拆分一下。

首先定义一个辅助函数 count_leq(bound)：统计数组中，最大值 ≤ bound 的连续子数组个数。

这时你会发现一个非常美妙的公式：

最大值在 [left, right] 的子数组个数 = 最大值 ≤ right 的子数组个数 − 最大值 ≤ (left - 1) 的子数组个数

为什么这个公式成立？

• “最大值 ≤ right” 这个集合里，包含了我们想要的（最大值在 [left, right] 的），也包含了我们不想要的（最大值 < left 的）。
• “最大值 ≤ left - 1” 这个集合里，只包含我们不想要的那些（最大值 < left 的）。
• 两者相减，刚好就把“太小的那些”剔除了，剩下的正是我们需要的。

于是，整个问题的核心就变成了：如何在线性时间 O(n) 内高效地计算出 count_leq(bound)？

单次扫描搞定 count_leq(bound)

计算这个函数的思路其实很直接。我们从左到右扫描一遍数组，并维护一个变量 cur。这个 cur 表示 以当前扫描到的元素为结尾，且子数组最大值 ≤ bound 的连续子数组有多少个。

扫描时的规则很简单，只有两条：

1. 如果当前元素 x 满足 x <= bound：
   • 那么它可以“接在”前面所有以 bound 为结尾的合法子数组后面，形成新的合法子数组。
   • 它也可以自己单独作为一个新的合法子数组。
   • 因此，cur 的值需要加 1（cur += 1）。
2. 如果当前元素 x 大于 bound (x > bound)：
   • 那么任何包含 x 的子数组，其最大值都大于 bound，不合法。
   • 所有以当前 x 结尾的合法子数组数量瞬间清零。
   • 因此，cur 需要被重置为 0（cur = 0）。

在每一步扫描中，我们都把当前的 cur 累加到最终答案 ans 里。这是因为：对于每个位置 i，“以 i 结尾的合法子数组个数”就等于这一步“新增”的合法子数组数量。

根据这个思路，count_leq 函数的代码实现如下：

def count_leq(nums, bound):
    ans = 0
    cur = 0
    for x in nums:
        if x <= bound:
            cur += 1  # 新增的合法子数组，都以当前 x 结尾
        else:
            cur = 0   # 被一个大于 bound 的数打断
        ans += cur
    return ans

整个过程只遍历数组一次，时间复杂度是 O(n)，空间复杂度是 O(1)。

完整解决方案

将上述所有步骤串联起来，就得到了完整的 Python 解决方案：

from typing import List

def count_leq(nums: List[int], bound: int) -> int:
    """
    统计 nums 中，最大值 <= bound 的连续子数组个数
    """
    ans = 0
    cur = 0
    for x in nums:
        if x <= bound:
            cur += 1
        else:
            cur = 0
        ans += cur
    return ans

def num_subarray_bounded_max(nums: List[int], left: int, right: int) -> int:
    """
    返回最大值在 [left, right] 区间内的子数组个数
    """
    # 最大值 <= right 的子数组数目
    total_leq_right = count_leq(nums, right)
    # 最大值 <= left - 1 的子数组数目（也就是最大值 < left）
    total_lt_left = count_leq(nums, left - 1)
    # 两者相减，剩下的就是最大值在 [left, right] 的
    return total_leq_right - total_lt_left

if __name__ == "__main__":
    nums = [2, 1, 4, 3]
    left, right = 2, 3
    print(num_subarray_bounded_max(nums, left, right))  # 输出 3

复杂度分析：

• 时间复杂度：count_leq 函数是 O(n)，主函数调用两次，总体仍是 O(n)。
• 空间复杂度：只使用了常数个额外变量，为 O(1)。

总结

这道“区间子数组个数”题目的核心解题思路分两步：

1. 转换问题：利用“全集减补集”的思想，将统计特定区间最大值的问题，转化为计算两个“最大值 ≤ 某值”的子问题。
2. 高效计数：通过一次线性扫描，用变量 cur 动态维护以当前位置结尾的合法子数组数，从而在 O(n) 时间内完成 count_leq 函数。

掌握这种“计数函数+差值”的思路，对于解决许多类似的区间统计问题非常有帮助。大家可以在 云栈社区 找到更多此类算法题的讨论和变种解法，与更多开发者一起交流成长。