0795. Number of Subarrays with Bounded Maximum¶
题目信息¶
- 题号:
0795
- 难度:
Medium
- 主题:
数组、连续子数组、最大值范围
- 原题:
- 重点:
统计非空连续子数组,条件只要求子数组最大值落在闭区间
[left, right];数组中小于left的元素可以包含在合法子数组中
题目重述¶
给定整数数组 nums 和两个整数 left、right,其中 left <= right。请统计有多少个非空连续子数组满足:该子数组中的最大元素位于闭区间 [left, right] 内。
子数组必须由原数组中一段连续元素组成。子数组可以包含小于 left 的元素,只要至少存在一个元素使最大值不小于 left,并且所有元素都不大于 right。
1 <= nums.length <= 10^5,0 <= nums[i] <= 10^9,0 <= left <= right <= 10^9。答案保证在 32 位有符号整数范围内。
自建示例¶
大于上界的元素会截断可选范围:
输入:nums = [1,2,2,5,3], left = 2, right = 3
输出:6
解释:前半段 [1,2,2] 中有五个最大值为 2 的子数组:[1,2]、[1,2,2]、第一个 [2]、[2,2]、第二个 [2];末尾 [3] 也合法。元素 5 大于上界,任何包含它的子数组都不合法。
所有元素都低于下界:
输入:nums = [1,1], left = 2, right = 3
输出:0
解释:三个非空连续子数组分别是两个单元素 [1] 和 [1,1],它们的最大值都为 1,小于下界 2,因此没有合法子数组。