本文涉及的知识点
C++算法:滑动窗口及双指针总结
LeetCode795. 区间子数组个数
给你一个整数数组 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
题解
令任意符合条件的子数组为[i,j]则:
则nums[i…j]必须存在[left,right]间的值,且不存在大于right的值。 ⟺ \iff ⟺ 存在大于等于left的值,不存在大于right的值。
nums[i…j]存在大于left值的最小解为j1。
nums[i…j]存在大于right值的最小解为j2。
j<j1,最大值小于left,非法;j>=j2,最大值大于right,非法。
故:以i开头合法的子数组数量为:j2-j1。
如果nums[i…j]不存在大于等于left的值,则nums[i+1…j]也不一定存在。故i++,j不需要复位。 → \rightarrow → 时间复杂度:O(n)
如果j1 < i,则j1++。并找到第一个nums[j1] >= left。
j2类似。
代码
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
const int N = nums.size();
int ans = 0;
for (int i = 0, j1 = -1, j2 = -1; i < N; i++) {
if (j1 < i) {
j1++;
while ((j1 < N) && (nums[j1] < left))j1++;
}
if (j2 < i) {
j2++;
while ((j2 < N) && (nums[j2] <= right))j2++;
}
ans += j2 - j1;
}
return ans;
}
};
核心代码
vector<int> nums;
int left, right;
TEST_METHOD(TestMethod11)
{
nums = { 2, 1, 4, 3 }, left = 2, right = 3;
auto res = Solution().numSubarrayBoundedMax(nums, left, right);
AssertEx(3, res);
}
TEST_METHOD(TestMethod12)
{
nums = { 2,9,2,5,6 }, left = 2, right =8;
auto res = Solution().numSubarrayBoundedMax(nums, left, right);
AssertEx(7, res);
}