科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文以 codeforces-go 仓库中 leetcode/biweekly/120/c/README.md 的官方题解为主体完整讲解 LeetCode 2972「删除不可增子数组 II」第 120 场双周赛 T3的 O(n) 双指针解法。读完你将掌握如何利用「严格递增前缀/后缀」的结构对移除方案分类计数、后缀枚举与左指针的单调收缩技巧、以及i2这一计数公式的推导同时结合仓库内的 Go 实现与测试用例理解该题解在本项目中的落地方式。问题回顾与仓库落点题目要求给定数组nums统计有多少个非空子数组可以被移除使得剩余部分可以为空是严格递增的。移除子数组后剩余部分由「一段前缀 一段后缀」拼接而成因此本题的核心是在保留严格递增的前缀和后缀的前提下统计可移除区间的个数。仓库中本题的完整题解位于 leetcode/biweekly/120/c/README.md对应实现为 c.go测试数据与测试代码分别为 c.txt 与 c_test.go。值得注意的是同场双周赛的 T1leetcode/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(n1)/2接下来讨论a不是严格递增数组的情况。可以移除如下后缀下标范围[i1, n-1]移除该后缀完整保留最长严格递增前缀[i, n-1][i-1, n-1]…[0, n-1]移除整个数组。这一共有i2个。例如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]即整个数组剩余元素为[]。一共i2 4个后缀。一般情况枚举保留的后缀双指针维护前缀边界核心思路移除子数组后剩下的部分是一个前缀加一个后缀需要满足前缀严格递增、后缀严格递增、且前缀的最后一个数严格小于后缀的第一个数。设后缀的第一个数为a[j]也就是说移除的子数组的最后一个数是a[j-1]。枚举j n-1, n-2, n-3, …, 1如果a[j] a[j1]则停止枚举。注意j不能为 0因为不能移除空数组。枚举j的同时维护最长前缀的最后一个数的下标i满足a[i] a[j]也就是说移除的子数组的第一个数的下标至多为i1。单调性是算法能保持 O(n) 的关键由于j越小a[j]越小a[i]也越小所以可以像滑动窗口那样不断左移i直到i 0或者a[i] a[j]为止。i与j都只会单调减小这正是「双指针」在此处的威力。类似移除后缀的情况对于固定的j可以移除如下子数组下标区间[i1, j-1][i, j-1][i-1, j-1]…[0, j-1]这一共有i2个。注意i -1时只能移除 1 个子数组即[0, j-1]同样符合i2这个结论因为(-1)2 1。累加这些i2即为答案。一个值得注意的边界细节由于不能移除空数组i与j的中间至少要有一个数所以必须要有i j-2。但是i j-1的情况说明a是严格递增数组已经在前面特判过了因此代码中无需再判断i与j-2的大小关系。多语言实现完整版以下是题解中给出的完整实现覆盖 Python3 / Java / C / C / Go / JavaScript / Rust 七种语言。所有版本遵循同一套逻辑先求最长严格递增前缀边界i特判整体严格递增再枚举保留的后缀a[j:]左移i并累加i2。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 # 不保留后缀的情况一共 i2 个 # 枚举保留的后缀为 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[:i1], a[:i], ..., a[:0] 一共 i2 个 ans i 2 j - 1 return ansclass 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; // 不保留后缀的情况一共 i2 个 // 枚举保留的后缀为 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[:i1], a[:i], ..., a[:0] 一共 i2 个 ans i 2; } return ans; } }class Solution { public: long long incremovableSubarrayCount(vectorint 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; // 不保留后缀的情况一共 i2 个 // 枚举保留的后缀为 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[:i1], a[:i], ..., a[:0] 一共 i2 个 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; // 不保留后缀的情况一共 i2 个 // 枚举保留的后缀为 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[:i1], a[:i], ..., a[:0] 一共 i2 个 ans i 2; } return ans; }func incremovableSubarrayCount(a []int) int64 { n : len(a) i : 0 for i n-1 a[i] a[i1] { i } if i n-1 { // 每个非空子数组都可以移除 return int64(n) * int64(n1) / 2 } ans : int64(i 2) // 不保留后缀的情况一共 i2 个 // 枚举保留的后缀为 a[j:] for j : n - 1; j n-1 || a[j] a[j1]; j-- { for i 0 a[i] a[j] { i-- } // 可以保留前缀 a[:i1], a[:i], ..., a[:0] 一共 i2 个 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; // 不保留后缀的情况一共 i2 个 // 枚举保留的后缀为 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[:i1], a[:i], ..., a[:0] 一共 i2 个 ans i 2; } return ans; };impl Solution { pub fn incremovable_subarray_count(a: Veci32) - 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; // 不保留后缀的情况一共 i2 个 // 枚举保留的后缀为 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[:i1], a[:i], ..., a[:0] 一共 i2 个 ans i 2; j - 1; } ans } }复杂度分析时间复杂度O(n)其中 n 为nums的长度。注意二重循环中的下标i和j都只会减小、不会变大由于下标只会减小 O(n) 次所以二重循环的总循环次数是 O(n) 的。空间复杂度O(1)仅使用常数个辅助变量。仓库源码佐证实现与测试仓库中的 c.go 与题解中的 Go 版本逻辑完全一致先求最长严格递增前缀边界i并特判整体递增此时直接返回n*(n1)/2再以ans i 2初始化「不保留后缀」的方案数随后枚举保留的后缀双指针收缩i并累加。唯一边界差异是仓库实现将外层循环写成j 0 (j n-1 || a[j] a[j1])显式保证j 1与题解中「j 不能为 0不能移除空数组」的约束保持一致。测试数据位于 c.txt包含三个用例[1,2,3,4]→10整体严格递增n(n1)/2 10所有非空子数组均可移除[6,5,7,8]→7[8,7,6,6]→3。测试入口 c_test.go 调用了仓库自研的 testutil.RunLeetCodeFuncWithFile该函数按「每 fNumInfNumOut 行一组」的方式解析测试文件再交给 RunLeetCodeFuncWithExamples 通过反射逐用例调用被测函数并与期望输出比对同时支持超时检测。这类测试模板由 copypasta/template/leetcode/generator_test.go 生成是仓库「题解 样例对拍」工作流的典型范式。同场 T1 与 T3 的对照第 120 场双周赛 T1leetcode/biweekly/120/a/a.go与本题同名同逻辑但返回类型为int且无显式的j 0守卫数据规模小语义等价的写法即可通过。对照阅读 a.go 与 c.go 的差异可以直观看到同一算法在「小数据范围 vs 大数据范围需int64」下的工程处理方式。变形与延伸从「计数」到「求最短/区间删除」本题的框架前缀/后缀单调性 双指针可以迁移到同类问题移除的子数组最短长度是多少即 LeetCode 1574「删除最短的子数组使剩余数组有序」同样是「严格递增前缀 严格递增后缀」的结构只不过计数改为最小化移除区间长度枚举策略类似但维护的目标从「方案个数」变为「区间长度的最小值」。改为移除所有元素值在[L,R]内的元素使得移除后剩余元素非降问有多少个(L,R)数对。这是 Codeforces 1167E「Range Deleting」仓库对应题解位于 main/1100-1199/1167E.go。两题的核心相通都是利用「删除一段连续区间后两侧剩余部分必须各自有序且衔接有序」的单调结构只是 1167E 将「按值区间删除」转化为对值域边界(L,R)的计数。小结本题的优雅之处在于把「统计所有可移除子数组」这一表面上的 O(n²) 枚举通过两个单调指针压缩到 O(n)结构分析剩余部分 严格递增前缀 严格递增后缀 严格递增衔接分类计数先算「只保留前缀」的i2种后缀移除再枚举保留的后缀并累加「保留前缀的i2种选择」单调性保证i、j均单向移动总移动次数 O(n)。配合仓库中的 c.go、c.txt 与 c_test.go读者可以本地运行go test复现全部样例并在此基础上继续钻研 1574 与 CF1167E 两个变形题把这套「有序结构 双指针」的套路内化为解题直觉。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐一条命令免费激活 Win11MAS 激活脚本四种免密钥方法Windows 与 Office 一次搞定一条命令免费激活 Win11MAS 激活脚本四种免密钥方法Windows 与 Office 一次搞定 MAS 激活脚本是面向 Win11 免费激活与 Off操作系统LeetCode 1574 删除最短的子数组使剩余数组有序双指针 滑动窗口解法深度解析LeetCode 1574 删除最短的子数组使剩余数组有序双指针 滑动窗口解法深度解析 导读 本篇基于开源仓库 leetcode https://link文档教程知识库LeetCode 最长严格递增或严格递减子数组Longest Strictly Increasing or Strictly Decreasing Subarray四解法详解LeetCode 最长严格递增或严格递减子数组Longest Strictly Increasing or Strictly Decreasing Subar示例工程教程上一篇Copilot for Xcode 自定义工具完整指南三步给 AI 助手装上会干活的手下一篇焦点堆栈技术深度解析从多焦点图像到全清晰3D重建的专业方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考