答案 = countSubarraysWithMaxAtMost(right) - countSubarraysWithMaxAtMost(left-1)

线性动态规划：统计优美子数组的个数（Number of Subarrays with Bounded Maximum） 题目描述 给定一个整数数组 nums 和两个整数 left 与 right （其中 left <= right ），要求统计数组中“最大值在区间 [left, right] 内”的连续子数组的个数。 换句话说，你需要计算所有满足以下条件的连续子数组 nums[i..j] 的数目： 子数组中的最大值 max(nums[i..j]) 满足 left ≤ max(nums[i..j]) ≤ right 。 示例 输入： nums = [2, 1, 4, 3] ， left = 2 ， right = 3 输出： 3 解释： 子数组 [2] 的最大值为 2，满足条件。 子数组 [3] 的最大值为 3，满足条件。 子数组 [2, 1] 的最大值为 2，满足条件。 注意： [4] 的最大值为 4 不在 [2,3] 内，不计数。 解题思路 我们可以将问题转化为“计算最大值不超过 right 的子数组个数”减去“计算最大值不超过 left-1 的子数组个数”，即： 这是因为： 最大值在 [left, right] 内的子数组 = 最大值 ≤ right 的子数组 − 最大值 ≤ left-1 的子数组。 关键步骤 ：如何高效计算“最大值不超过某值 maxVal 的连续子数组个数”？ 步骤详解 步骤 1：定义辅助函数 定义函数 countAtMost(maxVal) ，返回 nums 中所有“最大值 ≤ maxVal”的连续子数组的个数。 步骤 2：计算 countAtMost(maxVal) 考虑数组中的每个元素： 如果 nums[i] ≤ maxVal ，它可以作为当前“有效子数组”的一部分。 如果 nums[i] > maxVal ，它破坏了连续性，因为包含它的任何子数组的最大值都会超过 maxVal 。 我们可以用 双指针 （滑动窗口）来统计： 维护一个窗口 [l, r] ，使得窗口内所有元素都 ≤ maxVal 。 当 nums[r] ≤ maxVal 时，窗口向右扩展。 当遇到 nums[r] > maxVal 时，左指针 l 移动到 r+1 ，重新开始。 对于当前窗口，以右端点 r 结尾的、满足最大值 ≤ maxVal 的子数组个数为 r - l + 1 （即从 l 到 r 的所有起点都满足条件）。 举例 ： nums = [2, 1, 4, 3] ， maxVal = 3 r=0: 窗口[ 0,0]，计数 1（子数组[ 2 ]）。 r=1: 窗口[ 0,1]，计数 2（新增[ 2,1]、[ 1 ]）。 r=2: nums[ 2 ]=4 > 3，重置 l=3，窗口为空，计数 0。 r=3: 窗口[ 3,3]，计数 1（子数组[ 3 ]）。 总计数 = 1+2+0+1 = 4，即最大值不超过 3 的子数组共有 4 个。 步骤 3：计算答案 计算 countAtMost(right) 得到 A 。 计算 countAtMost(left-1) 得到 B 。 答案 = A - B 。 示例演算 给定 nums = [2, 1, 4, 3] ， left = 2 ， right = 3 。 计算 countAtMost(3) （如上）：得到 4。 计算 countAtMost(1) ： r=0: nums[ 0 ]=2>1，l=1，计数 0。 r=1: nums[ 1]=1≤1，窗口[ 1,1]，计数 1（子数组[ 1 ]）。 r=2: nums[ 2 ]=4>1，l=3，计数 0。 r=3: nums[ 3 ]=3>1，l=4，计数 0。 总计 1。 答案 = 4 − 1 = 3，与示例一致。 复杂度分析 时间复杂度：O(n)，其中 n 是数组长度。我们遍历两次数组分别计算 countAtMost(right) 和 countAtMost(left-1) ，每次遍历是 O(n)。 空间复杂度：O(1)，只用了常数变量。 扩展思考 若题目改为“最大值严格在区间 [left, right] 内”，只需将 countAtMost(right) - countAtMost(left-1) 中的 left-1 改为 left 即可。 此方法利用“区间计数减法”将原问题转化为更易处理的“最大值不超过某值”的子问题，是线性动态规划中 通过转化问题简化状态定义 的典型技巧。