Problem: 795. 区间子数组个数

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

示例 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

思路

• 思路本质和官方题解的一次遍历做法一样。
• 我看到区间就往树状数组想，确实能做，没想到ac完看到官方题解，时间、空间复杂度很少就ac了。所以就当为此题提供一种新的解决方法吧。

复杂度

时间复杂度:

$O(nlogn)$

空间复杂度:

$O(n)$

Code

const int MAX = 1e5+5;
int tr[MAX];
int lowbit(int x){return x&-x;}
void add(int x,int val){for(;x<MAX;x+=lowbit(x))tr[x]+=val;
}
// query表示的状态：以这个数作末尾有几种情况
int query(int x){int res=0;for(;x>0;x-=lowbit(x)){res+=tr[x];}return res;
}
class Solution {
public:// 单个区间的子数组个数（已保证该区间的所有数都<=right）int numArray(vector<int>& nums, int left) {memset(tr,0,sizeof(tr));int res=0;int lastIndex=-1;// lastIndex记录符合[left,right]的数的下标，不断更新for(int i=1;i<=nums.size();++i){// 树状数组下标从1开始add(i,1);// 如果数字小于left，就往左找到第一个符合[left,right]的数，结果加上他本身存在的情况数if(nums[i-1]<left&&lastIndex!=-1)res+=query(lastIndex);// 如果数字符合[left,right]，则总数加上以这个数作末尾的情况if(nums[i-1]>=left){res+=query(i);lastIndex=i;}}return res;}int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {int res=0;// 利用每个大于right的数去划分，得到多个子区间，对每个区间都使用numArray去计算该区间的数量，最后累加即可vector<int>tmp;for(auto num:nums){if(num<=right)tmp.emplace_back(num);else{if(tmp.size()>0){res+=numArray(tmp,left);tmp.clear();}}}if(tmp.size()>0){res+=numArray(tmp,left);tmp.clear();}return res;}
};