线性动态规划：统计优美子数组的个数（Number of Subarrays with Bounded Maximum）

题目描述

给定一个整数数组 nums 和两个整数 left 与 right，你需要统计并返回数组中最大值在区间 [left, right] 内的非空连续子数组的个数。

换句话说，对于任意子数组 nums[i..j]（其中 0 ≤ i ≤ j < n），如果其最大值 max(nums[i..j]) 满足 left ≤ max(nums[i..j]) ≤ right，则这个子数组是有效的。要求统计所有这样的子数组的个数。

示例
输入：nums = [2, 1, 4, 3]，left = 2，right = 3
输出：3
解释：有效的子数组有 [2]，[2, 1]，[3]，其他子数组的最大值都不在 [2,3] 区间内。
（注意：[2, 1] 的最大值是 2，在区间内；[4] 的最大值 4 不在区间内；[3] 是有效的。）

解题思路

1. 问题重述

我们不是直接枚举所有子数组并计算其最大值（那会需要 O(n³) 或 O(n²) 的时间），而是要通过一种更聪明的方法，利用线性扫描与递推关系在 O(n) 时间内解决。

关键观察：

• 如果一个子数组的最大值大于 right，则它无效。
• 如果一个子数组的最大值小于 left，它也无效吗？
  注意：题目要求是最大值在 [left, right] 内，所以如果子数组的最大值小于 left，那么它肯定无效。
  但这里有一个重要的转化思路。

2. 转化思路

设函数 count(nums, bound) 表示数组中最大值 ≤ bound 的子数组的个数。
那么题目所求为：

count(nums, right) - count(nums, left - 1)

为什么呢？

• count(nums, right) 是最大值 ≤ right 的子数组个数。
• count(nums, left - 1) 是最大值 ≤ left-1 的子数组个数。
• 两者相减，得到的就是最大值在 [left, right] 内的子数组个数。

于是问题转化为：如何高效计算 count(nums, bound)？

3. 计算 count(nums, bound)

对于固定的 bound，我们要找出所有最大值 ≤ bound 的子数组。

关键观察：
如果某个元素 nums[i] > bound，那么任何包含 nums[i] 的子数组的最大值肯定 > bound，因此这样的子数组都不符合条件。
所以，数组会被这些“坏元素”（nums[i] > bound）切分成若干段，每一段内所有元素都 ≤ bound。

在每一段内，任意连续子数组都满足最大值 ≤ bound。
假设一段的长度为 len，那么这一段能贡献的子数组个数为 len * (len + 1) / 2（从该段中任选 i 和 j，i ≤ j，得到的子数组都有效）。

例子：nums = [2, 1, 4, 3]，bound = 3
坏元素是 4（>3），它把数组切成：

• 段1: [2, 1] 长度 2 → 贡献 2*3/2 = 3 个子数组
• 段2: [3] 长度 1 → 贡献 1*2/2 = 1 个子数组
  总 = 4。
  即 count(nums, 3) = 4。

同理，bound = 1：
坏元素是 2,4,3（>1），切成的段全是长度 1 的？不对，nums[1]=1 ≤1，所以看哪些元素 ≤1：只有 nums[1]=1，其他都 >1，所以段只有 [1] 长度 1 → 贡献 1 个子数组。
所以 count(nums, 1) = 1。

题目例子：count(nums, 3) - count(nums, 1) = 4 - 1 = 3，与示例一致。

4. 高效计算 count(nums, bound) 的递推方法

我们不需要显式地分段然后求和公式，可以一次遍历完成：

遍历数组，维护当前连续“好元素”（≤ bound）的长度 cur_len。
当遇到 nums[i] ≤ bound 时，cur_len += 1，并且以 i 结尾的、最大值 ≤ bound 的子数组正好有 cur_len 个（从 i-cur_len+1 到 i 这些起始位置）。
所以直接累加 cur_len 到总数即可。

当遇到 nums[i] > bound 时，cur_len = 0。

例子：nums = [2, 1, 4, 3]，bound = 3
i=0: 2 ≤ 3 → cur_len=1, 总数+=1 → total=1
i=1: 1 ≤ 3 → cur_len=2, 总数+=2 → total=3
i=2: 4 > 3 → cur_len=0, 总数不变
i=3: 3 ≤ 3 → cur_len=1, 总数+=1 → total=4
得到 count=4。

5. 最终算法步骤

1. 实现函数 countLessEqual(nums, bound)：
   • 初始化 total = 0, cur_len = 0
   • 遍历 nums：
     • 如果 nums[i] ≤ bound：cur_len += 1，total += cur_len
     • 否则：cur_len = 0
   • 返回 total
2. 答案为 countLessEqual(nums, right) - countLessEqual(nums, left - 1)

时间复杂度：O(n)
空间复杂度：O(1)

6. 举例验证

nums = [2, 1, 4, 3], left=2, right=3
step1: count(nums, 3) = 4（上面已算）
step2: count(nums, 1) = 1（上面已算）
step3: 4 - 1 = 3 ✅

7. 边界情况考虑

• 如果 left > right：题目保证 left ≤ right
• 如果 nums 为空：返回 0
• 如果 left-1 可能为负数：函数里 bound 为负数时，所有元素都 > bound，所以 count=0

8. 代码框架（Python）

def numSubarrayBoundedMax(nums, left, right):
    def count(bound):
        total = 0
        cur = 0
        for num in nums:
            if num <= bound:
                cur += 1
                total += cur
            else:
                cur = 0
        return total
    
    return count(right) - count(left - 1)

总结

这道题的核心技巧是将“最大值在 [left, right]”转化为“最大值 ≤ right 的子数组数 减去 最大值 ≤ left-1 的子数组数”，然后对每个 bound 用一次遍历统计所有最大值 ≤ bound 的子数组个数。
统计时利用“连续好元素段”的性质，在遍历中累加以当前元素结尾的有效子数组数，达到 O(n) 时间 O(1) 空间的最优解。