795. 区间子数组个数 #

链接 #

题目 #

给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

示例 1：

输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]

示例 2：

输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= left <= right <= 109

解答 #

解决这个问题的一个有效方法是使用双指针或滑动窗口的思想。我们可以遍历数组，同时记录满足条件的子数组数量。关键在于理解如何统计符合条件的子数组个数。我们可以分别统计以每个元素结尾的、满足最大元素小于等于 right 的子数组数量，然后减去以每个元素结尾的、满足最大元素小于等于 left - 1 的子数组数量。这样，就能得到以每个元素结尾、其最大元素在 [left, right] 范围内的子数组数量。

下面是具体的实现步骤：

定义一个函数 count，用于计算以每个元素结尾，最大元素不超过某个值的子数组数量。
遍历数组，使用该函数分别计算最大元素不超过 right 和 left - 1 的子数组数量。
两者的差值即为最终答案。

具体代码如下：

def numSubarrayBoundedMax(nums, left, right):
    def count(bound):
        # 初始化计数器和子数组的开始索引
        ans = cur = 0
        for x in nums:
            # 如果当前元素小于等于bound，更新cur计数器
            cur = cur + 1 if x <= bound else 0
            # 累加到ans中
            ans += cur
        return ans

    # 计算最大元素不超过right的子数组数量，减去最大元素不超过left-1的子数组数量
    return count(right) - count(left - 1)

# 示例
print(numSubarrayBoundedMax([2,1,4,3], 2, 3))  # 输出：3
print(numSubarrayBoundedMax([2,9,2,5,6], 2, 8))  # 输出：7

这段代码中，count 函数通过遍历数组并利用变量 cur 来统计以每个元素结尾且最大元素不超过给定界限的子数组数量。最后，通过计算 count(right) - count(left - 1) 得到最终答案。这种方法的时间复杂度为 (O(N))，其中 (N) 是数组 nums 的长度，因为我们只需要遍历数组两次。

使用 left - 1 作为边界进行计算的原因是为了正确处理最大元素恰好等于 left 的情况。我们的目标是找出最大元素在区间 [left, right] 内的子数组数量。为了达到这个目的，我们实际上需要计算两部分：

最大元素小于等于 right 的子数组数量，这部分包括了所有最大元素不超过 right 的子数组，即最大元素在 [left, right] 内以及小于 left 的子数组。
最大元素小于等于 left - 1 的子数组数量，这部分包括了所有最大元素严格小于 left 的子数组。

通过从第一部分减去第二部分，我们排除了所有最大元素小于 left 的子数组，因此剩下的就是最大元素在 [left, right] 范围内的子数组数量。

这里为什么要选择 left - 1 而不直接是 left 呢？考虑到我们需要包含最大元素恰好等于 left 的子数组。如果我们使用 left 作为第二部分的边界，那么最大元素等于 left 的子数组会被错误地排除掉，因为这些子数组既不会被包含在最大元素小于等于 right 的计数中，也不应该被包含在最大元素小于 left 的计数中。通过计算最大元素小于等于 left - 1 的子数组数量，我们确保所有最大元素至少为 left 的子数组（包括最大元素恰好等于 left 的情况）都被正确计算在内。

public class Solution {
    public int NumSubarrayBoundedMax(int[] nums, int left, int right)
    {
        // 计算在集合 nums 中，连续子序列的元素值小于或等于 bound 的总数
        int Count(int bound)
        {
            int ans = 0;
            int cur = 0;
            foreach (int x in nums)
            {
                cur = x <= bound ? cur + 1 : 0;
                ans += cur;
            }
            return ans;
        }

        return Count(right) - Count(left - 1);
    }
}