题目描述：

给定一个整数数组 A 和两个整数 L 和 R，你需要找到数组中有多少个子数组的元素都在 [L, R] 的范围内。

  • 注意：子数组是连续的。

  • 示例

输入：A = [1, 2, 1, 2, 1], L = 2, R = 3 输出：5 解释：有效的子数组为 [2], [2], [1, 2], [2, 1], [2, 1, 2]。

输入：A = [2, 1, 4, 3], L = 2, R = 3 输出：3 解释：有效的子数组为 [2], [3], [2, 1]。

解题思路

可以通过计算满足条件的子数组的数量来解决此问题。我们可以使用以下步骤：

  1. 划分子数组： 将 A 划分为多个部分，每个部分内部的元素都在 [L, R] 之间。
  2. 计算每个部分的有效子数组数量： 对于每个有效的部分，使用公式计算子数组的数量。如果这个部分的长度为 n，那么有效的子数组数量为 n * (n + 1) / 2。
  3. 处理无效元素： 当遇到不在 [L, R] 范围内的元素时，重置当前的有效子数组计数。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
        def count_bound(max_val):
            count = 0
            total = 0
            for num in A:
                if num <= max_val:
                    count += 1
                else:
                    count = 0
                total += count
            return total
        
        return count_bound(R) - count_bound(L - 1)

复杂度分析

时间复杂度: O(n)，其中 n 是数组 A 的长度。我们只遍历 A 两次。

空间复杂度: O(1)，只使用常量空间。