题目链接：2970. 统计移除递增子数组的数目 I（简单？）

算法原理：

👉对应LeetCode题解

先给简单打个问号吧，因为这题说中等一点不为过，思路很难想，LeetCode给定义个简单感觉纯纯是因为暴力枚举能通过，但暴力枚举其实也不好想😅

2972. 统计移除递增子数组的数目 II直接难度飙升到困难了，题目一模一样，就是数据量不同，Ⅱ的暴力枚举会超时而已😂

自己在做了20多道双指针的题后，自己做的心路历程👇但最终还是失败了，没搞出来😭

解法一：暴力枚举

击败8.11%

时间复杂度O(n³)

官方题解给的思路很明白了，相信大家都能看懂

但是官方题解的代码没有注释很难懂，因为代码的思路跟上面的思路偏差还是有点大的，大家可以在Java代码部分看注释，我写的很清楚了，大家理解起来应该没问题

解法二：双指针

击败59.46%

时间复杂度O(n)

鉴于很多小伙伴也觉得官方题解有点晦涩难懂，所以博主亲自一点点用笔记推导出来了整个过程，一边看题解一边对照我的笔记，一遍就能顺通啦~（我也是一边看题解一边推导才弄懂的😭😭😭）

最后一个if语句的图解👇

if(nums[r]>=nums[r+1]) break;

与代码一一对应的过程全放在下面的Java代码中的注释里啦~

Java代码：

class Solution {
    //解法一：暴力枚举
    public int incremovableSubarrayCount(int[] nums) {
        int n=nums.length;
        int ret=0;
        for(int i=0;i<n;i++)
            for(int j=i;j<n;j++)
                if(isincreasing(nums,i,j))
                    ret++;
        return ret;
    }
    public boolean isincreasing(int[] nums,int left,int right){
        for(int i=1;i<nums.length;i++){
            //跳过[left,right+1]这个区间，因为这个区间是要移除的，不需要检查原数
            //为啥右边界是right+1?因为是通过right+1来确定是否调整right的，这也是为什么要从1开始遍历的原因
            if(i>=left&&i<=right+1) continue;
            //检查区间外的元素，如果有前数>=后数，直接false，删也白删
            if(nums[i-1]>=nums[i]) return false;
        }
        //检查边界衔接：必须满足nums[left-1]<nums[right+1]
        //先确保left-1和right+1不越界，再判断大小关系
        if(left-1>=0&&right+1<nums.length&&nums[right+1]<=nums[left-1]) return false;
        return true;
    }
}

class Solution {
    public int incremovableSubarrayCount(int[] nums) {
        int n=nums.length;
        int ret=0;
        int l=1;
        //进行笔记的④部分
        //找最大的l，使[l,r]满足“移除递增子数组”
        while(l<n&&nums[l-1]<nums[l]) l++;
        //l<n的话把l也算上
        ret+=l+(l<n?1:0);
        //进行笔记的⑤部分
        //找右侧的r，使[r+1,n−1]单调递增
        for(int r=n-2;r>=0;r--){//n-1的部分上面已经累加完了
            //如果nums[l-1]和nums[r+1]不满足递增，就l--至nums[l-1]<nums[r+1]
            while(l>0&&nums[l-1]>=nums[r+1]) l--;
            //l<r的话把l也算上
            ret+=l+(l<=r?1:0);
            //nums[r]>=nums[r+1]说明r破坏了[r+1,n-1]的递增性了
            //r开始往右的区间已经不是递增了
            //此时左侧更小的r对应无效区间，必须用break跳出循环
            if(nums[r]>=nums[r+1]) break;
        }
        return ret;
    }
}