力扣795.区间子数组个数 | 树状数组解法

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55