leetcode:795. 区间子数组个数_cold_sun_的博客-爱代码爱编程
题目描述:
给定一个元素都是正整数的数组A
,正整数 L
以及 R
(L <= R
)。
求连续、非空且其中最大元素满足大于等于L
小于等于R
的子数组个数。
输入输出:
输入:
A = [2, 1, 4, 3]
L = 2
R = 3
输出: 3
解释: 满足条件的子数组: [2], [2, 1], [3].
注意:
L, R 和 A[i] 都是整数,范围在 [0, 10^9]。
数组 A 的长度范围在[1, 50000]。
思路:这道题就注意一点处理,L<=A<=R的A子集可以看作小于等于R的A子集减去小于L的A子集。至于A中求小于某个值的子集个数,遍历A中所有元素,每见到一个满足小于等于一个值的A元素,子集个数就要加上该元素之前连续的满足条件元素的个数(因为要求子集必须连续)。
代码如下:
class Solution
{
public:
int BoundedMax(vector<int> &A,int R)
{
int sum=0,count=0;
for(int i=0;i<A.size();i++)
{
if(A[i]<=R)
{
count++;
sum+=count;
}
else
count=0;
}
return sum;
}
int numSubarrayBoundedMax(vector<int> &A,int L,int R)
{
return BoundedMax(A,R)-BoundedMax(A,L-1);
}
};
为了减少内存开支可以多用引用(确保引用后的操作对你原变量的改变不会影响你的后续结果),因为引用的内存开支只有一个指针的大小。