• 科学计算

本文以 codeforces-go 仓库中 leetcode/biweekly/120/c/README.md 的官方题解为主体，完整讲解 LeetCode 2972「删除不可增子数组 II」（第 120 场双周赛 T3）的 O(n) 双指针解法。读完你将掌握：如何利用「严格递增前缀/后缀」的结构对移除方案分类计数、后缀枚举与左指针的单调收缩技巧、以及i+2这一计数公式的推导；同时结合仓库内的 Go 实现与测试用例，理解该题解在本项目中的落地方式。

问题回顾与仓库落点

题目要求：给定数组nums，统计有多少个非空子数组可以被移除，使得剩余部分（可以为空）是严格递增的。移除子数组后，剩余部分由「一段前缀 + 一段后缀」拼接而成，因此本题的核心是在保留严格递增的前缀和后缀的前提下，统计可移除区间的个数。

仓库中本题的完整题解位于 leetcode/biweekly/120/c/README.md，对应实现为 c.go，测试数据与测试代码分别为 c.txt 与 c_test.go。值得注意的是，同场双周赛的 T1（leetcode/biweekly/120/a/a.go）与本题为同名函数的弱化版：T1 返回int，数据规模较小；T3 返回int64，适配更大的数据范围。这在本仓库中对应两个独立文件，便于对照学习同一算法在不同规模下的写法差异。

下文为方便描述，将nums简记为a，长度为n，下标从 0 开始。

核心观察：剩余部分的结构

无论移除哪个子数组，移除后剩下的部分一定是「前缀 + 后缀」的形式。要使剩余部分严格递增，必须同时满足三个条件：

• 前缀是严格递增的；
• 后缀是严格递增的；
• 前缀的最后一个数严格小于后缀的第一个数。

这一观察把「移除子数组」等价转化为「保留一个严格递增前缀和一个严格递增后缀，且二者衔接处严格递增」，计数也因此有了清晰的分类框架。

第一步：只保留前缀——可以移除多少个后缀？

核心思路：如果移除的是后缀，那么移除后剩下的是前缀，且这个前缀必须是严格递增的。

设a的最长严格递增前缀的最后一个数是a[i]。例如a = [1,3,4,1,2]，最长严格递增前缀的最后一个数是a[2] = 4。

特判：如果i = n-1，说明a本身就是严格递增数组，那么任意非空子数组都可以移除，直接返回非空子数组的个数：

n(n+1)/2

接下来讨论a不是严格递增数组的情况。可以移除如下后缀（下标范围）：

• [i+1, n-1]：移除该后缀，完整保留最长严格递增前缀；
• [i, n-1]
• [i-1, n-1]
• …
• [0, n-1]：移除整个数组。

这一共有i+2个。

例如a = [1,3,4,1,2]，计算出的i = 2，可以移除：

• 下标范围[3,4]，即后缀[1,2]，剩余元素为[1,3,4]；
• 下标范围[2,4]，即后缀[4,1,2]，剩余元素为[1,3]；
• 下标范围[1,4]，即后缀[3,4,1,2]，剩余元素为[1]；
• 下标范围[0,4]，即整个数组，剩余元素为[]。

一共i+2 = 4个后缀。

一般情况：枚举保留的后缀，双指针维护前缀边界

核心思路：移除子数组后，剩下的部分是一个前缀加一个后缀，需要满足：前缀严格递增、后缀严格递增、且前缀的最后一个数严格小于后缀的第一个数。

设后缀的第一个数为a[j]，也就是说，移除的子数组的最后一个数是a[j-1]。

枚举j = n-1, n-2, n-3, …, 1，如果a[j] >= a[j+1]则停止枚举。注意j不能为 0，因为不能移除空数组。

枚举j的同时，维护最长前缀的最后一个数的下标i（满足a[i] < a[j]），也就是说，移除的子数组的第一个数的下标至多为i+1。

单调性是算法能保持 O(n) 的关键：由于j越小，a[j]越小，a[i]也越小，所以可以像滑动窗口那样不断左移i，直到i < 0或者a[i] < a[j]为止。i与j都只会单调减小，这正是「双指针」在此处的威力。

类似移除后缀的情况，对于固定的j，可以移除如下子数组（下标区间）：

• [i+1, j-1]
• [i, j-1]
• [i-1, j-1]
• …
• [0, j-1]

这一共有i+2个。注意i = -1时只能移除 1 个子数组，即[0, j-1]，同样符合i+2这个结论，因为(-1)+2 = 1。累加这些i+2，即为答案。

一个值得注意的边界细节：由于不能移除空数组，i与j的中间至少要有一个数，所以必须要有i <= j-2。但是i = j-1的情况说明a是严格递增数组，已经在前面特判过了，因此代码中无需再判断i与j-2的大小关系。

多语言实现（完整版）

以下是题解中给出的完整实现，覆盖 Python3 / Java / C++ / C / Go / JavaScript / Rust 七种语言。所有版本遵循同一套逻辑：先求最长严格递增前缀边界i，特判整体严格递增；再枚举保留的后缀a[j:]，左移i并累加i+2。

class Solution: def incremovableSubarrayCount(self, a: List[int]) -> int: n = len(a) i = 0 while i < n - 1 and a[i] < a[i + 1]: i += 1 if i == n - 1: # 每个非空子数组都可以移除 return n * (n + 1) // 2 ans = i + 2 # 不保留后缀的情况，一共 i+2 个 # 枚举保留的后缀为 a[j:] j = n - 1 while j == n - 1 or a[j] < a[j + 1]: while i >= 0 and a[i] >= a[j]: i -= 1 # 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个 ans += i + 2 j -= 1 return ans

class Solution { public long incremovableSubarrayCount(int[] a) { int n = a.length; int i = 0; while (i < n - 1 && a[i] < a[i + 1]) { i++; } if (i == n - 1) { // 每个非空子数组都可以移除 return (long) n * (n + 1) / 2; } long ans = i + 2; // 不保留后缀的情况，一共 i+2 个 // 枚举保留的后缀为 a[j:] for (int j = n - 1; j == n - 1 || a[j] < a[j + 1]; j--) { while (i >= 0 && a[i] >= a[j]) { i--; } // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个 ans += i + 2; } return ans; } }

class Solution { public: long long incremovableSubarrayCount(vector<int> &a) { int n = a.size(); int i = 0; while (i < n - 1 && a[i] < a[i + 1]) { i++; } if (i == n - 1) { // 每个非空子数组都可以移除 return (long long) n * (n + 1) / 2; } long long ans = i + 2; // 不保留后缀的情况，一共 i+2 个 // 枚举保留的后缀为 a[j:] for (int j = n - 1; j == n - 1 || a[j] < a[j + 1]; j--) { while (i >= 0 && a[i] >= a[j]) { i--; } // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个 ans += i + 2; } return ans; } };

long long incremovableSubarrayCount(int* a, int n) { int i = 0; while (i < n - 1 && a[i] < a[i + 1]) { i++; } if (i == n - 1) { // 每个非空子数组都可以移除 return (long long) n * (n + 1) / 2; } long long ans = i + 2; // 不保留后缀的情况，一共 i+2 个 // 枚举保留的后缀为 a[j:] for (int j = n - 1; j == n - 1 || a[j] < a[j + 1]; j--) { while (i >= 0 && a[i] >= a[j]) { i--; } // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个 ans += i + 2; } return ans; }

func incremovableSubarrayCount(a []int) int64 { n := len(a) i := 0 for i < n-1 && a[i] < a[i+1] { i++ } if i == n-1 { // 每个非空子数组都可以移除 return int64(n) * int64(n+1) / 2 } ans := int64(i + 2) // 不保留后缀的情况，一共 i+2 个 // 枚举保留的后缀为 a[j:] for j := n - 1; j == n-1 || a[j] < a[j+1]; j-- { for i >= 0 && a[i] >= a[j] { i-- } // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个 ans += int64(i + 2) } return ans }

var incremovableSubarrayCount = function(a) { const n = a.length; let i = 0; while (i < n - 1 && a[i] < a[i + 1]) { i++; } if (i === n - 1) { // 每个非空子数组都可以移除 return n * (n + 1) / 2; } let ans = i + 2; // 不保留后缀的情况，一共 i+2 个 // 枚举保留的后缀为 a[j:] for (let j = n - 1; j === n - 1 || a[j] < a[j + 1]; j--) { while (i >= 0 && a[i] >= a[j]) { i--; } // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个 ans += i + 2; } return ans; };

impl Solution { pub fn incremovable_subarray_count(a: Vec<i32>) -> i64 { let n = a.len(); let mut i = 0; while i < n - 1 && a[i] < a[i + 1] { i += 1; } if i == n - 1 { // 每个非空子数组都可以移除 return n as i64 * (n + 1) as i64 / 2; } let mut i = i as i64; let mut ans = i + 2; // 不保留后缀的情况，一共 i+2 个 // 枚举保留的后缀为 a[j:] let mut j = n - 1; while j == n - 1 || a[j] < a[j + 1] { while i >= 0 && a[i as usize] >= a[j] { i -= 1; } // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个 ans += i + 2; j -= 1; } ans } }

复杂度分析

• 时间复杂度：O(n)，其中 n 为nums的长度。注意二重循环中的下标i和j都只会减小、不会变大，由于下标只会减小 O(n) 次，所以二重循环的总循环次数是 O(n) 的。
• 空间复杂度：O(1)，仅使用常数个辅助变量。

仓库源码佐证：实现与测试

仓库中的 c.go 与题解中的 Go 版本逻辑完全一致：先求最长严格递增前缀边界i并特判整体递增（此时直接返回n*(n+1)/2），再以ans = i + 2初始化「不保留后缀」的方案数，随后枚举保留的后缀，双指针收缩i并累加。唯一边界差异是仓库实现将外层循环写成j > 0 && (j == n-1 || a[j] < a[j+1])，显式保证j >= 1，与题解中「j 不能为 0（不能移除空数组）」的约束保持一致。

测试数据位于 c.txt，包含三个用例：

• [1,2,3,4]→10：整体严格递增，n(n+1)/2 = 10，所有非空子数组均可移除；
• [6,5,7,8]→7；
• [8,7,6,6]→3。

测试入口 c_test.go 调用了仓库自研的 testutil.RunLeetCodeFuncWithFile：该函数按「每 fNumIn+fNumOut 行一组」的方式解析测试文件，再交给 RunLeetCodeFuncWithExamples 通过反射逐用例调用被测函数并与期望输出比对，同时支持超时检测。这类测试模板由 copypasta/template/leetcode/generator_test.go 生成，是仓库「题解 + 样例对拍」工作流的典型范式。

同场 T1 与 T3 的对照

第 120 场双周赛 T1（leetcode/biweekly/120/a/a.go）与本题同名同逻辑，但返回类型为int且无显式的j > 0守卫（数据规模小，语义等价的写法即可通过）。对照阅读 a.go 与 c.go 的差异，可以直观看到同一算法在「小数据范围 vs 大数据范围（需int64）」下的工程处理方式。

变形与延伸：从「计数」到「求最短/区间删除」

本题的框架（前缀/后缀单调性 + 双指针）可以迁移到同类问题：

1. 移除的子数组最短长度是多少？即 LeetCode 1574「删除最短的子数组使剩余数组有序」：同样是「严格递增前缀 + 严格递增后缀」的结构，只不过计数改为最小化移除区间长度，枚举策略类似，但维护的目标从「方案个数」变为「区间长度的最小值」。
2. 改为移除所有元素值在[L,R]内的元素，使得移除后剩余元素非降，问有多少个(L,R)数对。这是 Codeforces 1167E「Range Deleting」，仓库对应题解位于 main/1100-1199/1167E.go。两题的核心相通：都是利用「删除一段连续区间后两侧剩余部分必须各自有序且衔接有序」的单调结构，只是 1167E 将「按值区间删除」转化为对值域边界(L,R)的计数。

小结

本题的优雅之处在于把「统计所有可移除子数组」这一表面上的 O(n²) 枚举，通过两个单调指针压缩到 O(n)：

• 结构分析：剩余部分 = 严格递增前缀 + 严格递增后缀 + 严格递增衔接；
• 分类计数：先算「只保留前缀」的i+2种后缀移除，再枚举保留的后缀并累加「保留前缀的i+2种选择」；
• 单调性保证：i、j均单向移动，总移动次数 O(n)。

配合仓库中的 c.go、c.txt 与 c_test.go，读者可以本地运行go test复现全部样例，并在此基础上继续钻研 1574 与 CF1167E 两个变形题，把这套「有序结构 + 双指针」的套路内化为解题直觉。

• 科学计算