题目链接：2972. 统计移除递增子数组的数目 II（困难）

算法原理：

👉对应LeetCode题解

解法：双指针

击败40.79%

时间复杂度O(n)

跟B.双指针——2970. 统计移除递增子数组的数目 I的思路、代码完全相同，就是返回值从int改成了long（因为这个数据量猛增了，暴力枚举不能通过了），大家可以点开链接自行去查看我的那篇博客，推导的很详细了，以下👇只说明与官方题解（以下称新题解）的不同之处：

①左递增前缀的定义方式不同

旧题解：l 是左递增前缀的长度。例如，若 nums[0..l-1] 严格递增，则 l 是这个前缀的长度（末尾索引为 l-1）

新题解：l 是左递增前缀的最后一个索引。例如，若 nums[0..l] 严格递增，则 l 是这个前缀的末尾索引（长度为 l+1）

②初始结果的计算逻辑不同（统计 “只保留左前缀” 的子数组）

旧题解：初始 ret += l + (l < n ? 1 : 0)

含义：l 是左前缀长度（0..l-1 递增），基础数量为 l（移除 [i..n-1] 其中 i 从 1 到 l），若 l < n（左前缀不是整个数组），额外加 1（移除 [0..n-1]，剩余空），总计 l + (l < n ? 1 : 0)

新题解：初始 ans += l + 2

含义：移除的子数组可以是 [i..len-1]（i 从 0 到 l+1），共 l+2 种。例如：左前缀为 0..l，移除 [0..len-1]（剩余空）、[1..len-1]（剩余 0）、...、[l+1..len-1]（剩余 0..l），共 l+2 种

③右侧遍历的起点和条件不同（找右递增后缀）

旧题解：从 r = n - 2 开始向左遍历（因为 r = n - 1 对应的 “只保留右后缀” 已在②中覆盖），终止条件是 r >= 0

用 if (nums[r] >= nums[r + 1]) break 确保 r+1..n-1 是右递增后缀（r 破坏递增性则停止）

新题解：从 r = len - 1（数组末尾）开始向左遍历，终止条件是 r > 0

用 if (r < len - 1 && nums[r] >= nums[r + 1]) break 确保 r..len-1 是右递增后缀（一旦破坏递增性就停止）

④调整左前缀范围的逻辑不同（满足 “左前缀 + 右后缀” 拼接）

旧题解：对于右后缀起点 r+1（因 r 从 n-2 开始，r+1 是右后缀的第一个元素）

调整 l 使得 nums[l-1] < nums[r+1]（左前缀末尾 < 右后缀起点）

累加 l + (l <= r ? 1 : 0)（l 是左前缀长度，l <= r 时额外加 1 表示移除中间子数组的完整情况）

新题解：对于右后缀起点 r

调整 l 使得 nums[l] < nums[r]（左前缀末尾 < 右后缀起点）

累加 l + 2（含义同初始计算，对应移除中间子数组 [l+1..r-1] 的所有可能扩展）

Java代码：

class Solution {
//2970. 统计移除递增子数组的数目 I的题解代码，返回值改成long一样AC！
    public long incremovableSubarrayCount(int[] nums) {
        int n=nums.length;
        long 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;
    }
}

class Solution {
//官方新题解代码
    public long incremovableSubarrayCount(int[] nums) {
        long ans = 0;
        int len = nums.length;
        int l = 0;
        while (l < len - 1) {
            if (nums[l] >= nums[l + 1]) {
                break;
            }
            l++;
        }
        if (l == len - 1) {
            return 1L * len * (len + 1) / 2;
        }

        ans += l + 2;
        for (int r = len - 1; r > 0; r--) {
            if (r < len - 1 && nums[r] >= nums[r + 1]) {
                break;
            }
            
            while (l >= 0 && nums[l] >= nums[r]) {
                l--;
            }
            ans += l + 2;
        } 

        return ans;
    }
}