problem:2972. 统计移除递增子数组的数目 II

思路：找出最长递增前缀和最长的递减后缀，枚举删除[i,j]区间，可以枚举左端点，去找右端点不重不漏算完答案。

Accode：

滑动窗口

class Solution {
public:
    long long incremovableSubarrayCount(vector<int>& nums) {
        int len =nums.size();
        long long ans = 0;
        int left = len-1,right = 0;
        for(int i=0;i<len-1;i++){
            if(nums[i]>=nums[i+1]){
                left=i;
                break;
            }
        }
        for(int i=len-1;i>0;i--){
            if(nums[i-1]>=nums[i]){
                right = i;
                break;
            }
        }
        if(right==0){
            return len*(len+1)/2;
        }
        ans+=left+2;
        for(int i=0,j=right;j<len;j++){
            while(nums[i]<nums[j] && i<=left){
                i++;  
            }
            ans+=i+1;
        }
        return ans;
    }
};

时间复杂度：$o(n)$

二分

class Solution {
public:
    long long incremovableSubarrayCount(vector<int>& nums) {
        int len =nums.size();
        long long ans = 0;
        int left = len-1,right = 0;
        for(int i=0;i<len-1;i++){
            if(nums[i]>=nums[i+1]){
                left=i;
                break;
            }
        }
        for(int i=len-1;i>0;i--){
            if(nums[i-1]>=nums[i]){
                right = i;
                break;
            }
        }
        if(right==0){
            return len*(len+1)/2;
        }
        ans+=len-right+1;
        cout <<left<<endl;
        for(int i=0;i<=left;i++){
            int l = right-1,r = len;
            while(l+1!=r){
                int mid = (l+r)>>1;
                if(nums[mid]>nums[i]){
                    r = mid;
                }
                else l = mid;
            }
            ans+=1+len-r;
            cout << ans<<endl;
        }
        return ans;
        //6 6 5 7 8  4+3   
    }
};

时间复杂度：$o(n*logn)$