来源:力扣(LeetCode)
描述:
给你一个整数数组 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
提示:
方法一:一次遍历
思路与算法
一个子数组的最大值范围在 [left, right] 表示子数组中不能含有大于 right 的元素,且至少含有一个处于 [left, right] 区间的元素。
我们可以将数组中的元素分为三类,并分别用 0, 1, 2 来表示:
那么本题可以转换为求解不包含 2,且至少包含一个 1 的子数组数目。我们遍历 i,并将右端点固定在 i,求解有多少合法的子区间。过程中需要维护两个变量:
如果 last1 ≠ −1 ,那么子数组若以 i 为右端点,合法的左端点可以落在 (last2, last1] 之间。这样的左端点共有 last1 − last2个。
因此,我们遍历 i:
然后将 last1 − last2 累加到答案中即可。最后的总和即为题目所求。
代码:
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int res = 0, last2 = -1, last1 = -1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] >= left && nums[i] <= right) {
last1 = i;
} else if (nums[i] > right) {
last2 = i;
last1 = -1;
}
if (last1 != -1) {
res += last1 - last2;
}
}
return res;
}
};
复杂度分析
时间复杂度:O(n),其中 n 是 nums 的长度。整个过程只需要遍历一次 nums。
空间复杂度:O(1)。只使用到常数个变量。
方法二:计数
思路与算法
方法一提到,我们要计算的合法子区间不包含 2 且至少包含一个 1。所以,我们可以先求出只包含 0 或 1 的子区间数目,再减去只包括 0 的子区间数目。
设函数 count(nums,lower) 可以求出数组 nums 中所有元素小于等于 lower 的子数组数目,那么题目所求就是 count(nums, right) − count(nums, left)。
关于 count(nums,lower) 的实现,我们用 i 遍历 nums[i],cur 表示 i 左侧有多少个连续的元素小于等于 lower:
每次将 cur 加到答案中,最终的和即为 count 函数返回值。
代码:
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
return count(nums, right) - count(nums, left - 1);
}
int count(vector<int>& nums, int lower) {
int res = 0, cur = 0;
for (auto x : nums) {
cur = x <= lower ? cur + 1 : 0;
res += cur;
}
return res;
}
};
复杂度分析
时间复杂度: O(n),其中 n 是 nums 的长度。整个求解过程需要遍历两次 nums。
空间复杂度:O(1)。只使用到常数个变量。
author:力扣官方题解