千问 LeetCode 2972. 统计移除递增子数组的数目 II Java实现

针对 LeetCode 2972. 统计移除递增子数组的数目 II最优雅且高效的解法是使用双指针Two Pointers。核心思路移除一个子数组后剩余的元素必须严格递增。这意味着剩余的元素只能由原数组的严格递增前缀和严格递增后缀拼接而成且前缀的最后一个元素必须小于后缀的第一个元素。1. 特殊情况处理如果整个数组本身就是严格递增的那么移除任意一个子数组都满足条件。长度为 n 的数组共有 n times (n 1) / 2 个子数组直接返回该结果。2. 寻找最长递增前缀使用左指针 l 找到数组最长严格递增前缀的最后一个元素下标。3. 枚举后缀并匹配前缀使用右指针 r 从数组末尾向前枚举严格递增后缀的起始位置。对于每一个合法的 r不断向左移动 l直到满足 nums[l] nums[r]。4. 计算贡献当 nums[l] nums[r] 时以 r 为后缀起点的合法移除方案共有 l 2 种即移除 [0, r-1], [1, r-1], ..., [l, r-1], 以及 [l1, r-1]。Java 代码实现class Solution {public long incremovableSubarrayCount(int[] nums) {int n nums.length;int l 0;// 1. 寻找最长严格递增前缀的最后一个元素下标 lwhile (l n - 1 nums[l] nums[l 1]) {l;}// 2. 如果整个数组都是严格递增的直接返回所有子数组的个数if (l n - 1) {return (long) n * (n 1) / 2;}// 3. 初始化答案此时可以移除包含后缀的所有情况即保留空前缀只保留后缀// 包含移除 [0, n-1], [1, n-1], ..., [l, n-1], [l1, n-1]共 l 2 种long ans l 2;// 4. 从右向左枚举严格递增后缀的起点 rfor (int r n - 1; r 0; r--) {// 如果当前元素不满足严格递增后缀的条件说明往左也不再是递增后缀直接退出if (r n - 1 nums[r] nums[r 1]) {break;}// 移动左指针 l直到前缀末尾元素严格小于后缀起始元素while (l 0 nums[l] nums[r]) {l--;}// 此时保留前缀 [0...l] 和后缀 [r...n-1] 是合法的// 对应的移除子数组方案有[0, r-1], [1, r-1], ..., [l, r-1], [l1, r-1]// 总共贡献 l 2 种方案ans l 2;}return ans;}}复杂度分析* 时间复杂度O(n)。左指针 l 和右指针 r 最多各自遍历数组一次整体呈线性时间复杂度。* 空间复杂度O(1)。仅使用了几个指针和变量没有使用额外的数据结构。