科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文以 codeforces-go 仓库中第 82 场 LeetCode 双周赛 D 题LeetCode 2334Subarray With Elements Greater Than Varying Threshold的题解文档为骨架系统拆解「并查集 从大到小遍历」与「单调栈求左右边界」两种经典算法并对照仓库内的 Go 实现、测试用例与 copypasta 模板源码帮助你掌握如何把套路化的算法模板运用到实际比赛中。题目回顾判断是否存在满足条件的子数组给你一个整数数组nums和一个整数threshold要求判断是否存在长度至少为 1 的子数组使得该子数组内每个元素都大于threshold / k其中k是子数组的长度。存在则返回k否则返回-1。条件min(nums[l..r]) threshold / k等价于min(nums[l..r]) * k threshold。换句话说区间最小值与区间长度的乘积必须严格超过给定的阈值。这一约束同时涉及「区间最小值」与「区间长度」两个维度两者相互制约最小值大但区间短可能不够区间长但最小值小同样不满足。本题的两种标准解法正是针对这两个维度分别发起进攻——方法一从「值」入手从大到小逐个激活元素用并查集把激活过的相邻元素连成链方法二从「区间」入手用单调栈为每个元素框定它能作为最小值的最大区间。仓库对应题解文档位于 leetcode/biweekly/82/d/README.mdGo 代码实现位于 d.go。方法一并查集——从大到小激活元素用链长代表 k解题思路的四个提示原题解文档给出了四个层层递进的提示这里逐一展开提示 1数组中的元素越大越好不妨从大往小考虑nums[i]。因为条件只关心「子数组的最小值」最小值越大越容易满足要求所以按元素值从大到小的顺序逐个激活位置是自然的切入点。提示 2子数组的长度k越大threshold / k就越小越能满足要求。这说明在固定最小值时我们总是希望区间尽可能长。提示 3把考虑过的元素都串起来这条链的长度就是k。当按值从大到小激活位置后被激活的相邻位置会连成一整段而每个当前被激活的元素所能构成的、以它为最小值的最大区间正是它所在的连续激活段——段长即k。提示 4用并查集动态维护链长。遍历到nums[i]时用并查集把i和i1合并即可把连续访问过的位置串成一条链同时维护每条链的长度sz。核心不变量算法维护的关键不变量是当我们按值从大到小处理到某个元素num时所有值大于等于num的位置都已被激活并且已激活的相邻位置被并查集合并成若干连通块。对当前元素num而言它所在连通块的大小sz就是「以num为最小值」的最长连续区间长度k。于是每次激活后只需检查num threshold / sz是否成立为避免浮点误差写成整除/乘法形式成立即返回sz。由于我们是按值从大到小处理的第一个命中的k就是题目要找的答案。四种语言的完整实现Python3class Solution: def validSubarraySize(self, nums: List[int], threshold: int) - int: n len(nums) fa list(range(n 1)) sz [0] * (n 1) def find(x: int) - int: if fa[x] ! x: fa[x] find(fa[x]) return fa[x] # 按元素值从大到小排序同时保留原下标 for num, i in sorted(zip(nums, range(n)), reverseTrue): j find(i 1) # 找到 i1 所在链的链头 fa[i] j # 合并 i 和 i1让 i 指向右侧链头 sz[j] sz[i] 1 # 链长增加sz[i] 是 i 左侧已合并的部分 if num threshold // sz[j]: return sz[j] # 满足条件返回链长 return -1Javaclass Solution { int[] fa; public int validSubarraySize(int[] nums, int threshold) { var n nums.length; fa new int[n 1]; for (var i 0; i n; i) fa[i] i; // 初始时每个位置自成一条链 var sz new int[n 1]; // sz[i] 表示链的大小 // 按下标排序让 nums 值大的排在前面 var ids IntStream.range(0, n).boxed().toArray(Integer[]::new); Arrays.sort(ids, (i, j) - nums[j] - nums[i]); for (var i : ids) { var j find(i 1); // 右侧链的链头 fa[i] j; // 合并 i 和 i1 sz[j] sz[i] 1; if (nums[i] threshold / sz[j]) return sz[j]; } return -1; } int find(int x) { // 路径压缩 if (fa[x] ! x) fa[x] find(fa[x]); return fa[x]; } }Cclass Solution { public: int validSubarraySize(vectorint nums, int threshold) { int n nums.size(); int fa[n 1], sz[n 1]; iota(fa, fa n 1, 0); // 0,1,...,n memset(sz, 0, sizeof(sz)); functionint(int) find - int { return fa[x] x ? x : fa[x] find(fa[x]); }; int ids[n]; iota(ids, ids n, 0); sort(ids, ids n, { return nums[i] nums[j]; }); for (int i : ids) { int j find(i 1); fa[i] j; // 合并 i 和 i1 sz[j] sz[i] 1; if (nums[i] threshold / sz[j]) return sz[j]; } return -1; } };Gofunc validSubarraySize(nums []int, threshold int) int { n : len(nums) type pair struct{ v, i int } a : make([]pair, n) for i, v : range nums { a[i] pair{v, i} } sort.Slice(a, func(i, j int) bool { return a[i].v a[j].v }) // 按值从大到小 fa : make([]int, n1) for i : range fa { fa[i] i } sz : make([]int, n1) var find func(int) int find func(x int) int { if fa[x] ! x { fa[x] find(fa[x]) // 路径压缩 } return fa[x] } for _, p : range a { i : p.i j : find(i 1) // 右侧链的链头 fa[i] j // 合并 i 和 i1 sz[j] sz[i] 1 if p.v threshold/sz[j] { // 注意用除法避免浮点误差 return sz[j] } } return -1 }这段 Go 代码与仓库 d.go 中的validSubarraySize2完全一致是并查集解法的仓库原生实现。值得留意的是sz[j] sz[i] 1这句sz[i]保存的是i左侧已经并入i的链长因为左链的链头已经被指向i再加上i自身与右侧链头j一次find加一次赋值就完成了链的拼接这正是提示 3 所说「用并查集把链串起来」的落地细节。复杂度分析时间复杂度$\mathcal{O}(n\log n)$。瓶颈在排序上并查集部分每个位置只被合并一次路径压缩后接近线性。空间复杂度$\mathcal{O}(n)$。fa、sz数组各需n1的空间。仓库模板库 union_find.go 对并查集有系统总结只有路径压缩的并查集复杂度是O(n log n)也是大多数场景下的实现方案本题对fa的初始化、find的递归压缩写法与模板完全同构属于「按值离线激活 连通块大小维护」这一并查集经典套路的直接应用。方法二单调栈——为每个元素框定它当最小值的最大区间解题思路的提示提示 1枚举每个元素假设它是子数组中的最小值。任何子数组的最小值一定等于数组中某个元素因此只需对每个元素分别考察。提示 2子数组的左右边界最远能到哪以nums[i]为最小值允许并列的区间向左不能越过第一个更小的元素向右同样不能越过第一个更小的元素。提示 3用单调栈计算左右边界。对每个i用单调栈求出left[i]左侧最近的小于nums[i]的元素位置不存在为-1与right[i]右侧最近的小于nums[i]的元素位置不存在为n则k right[i] - left[i] - 1就是以nums[i]为最小值的最长子数组长度。这道题恰好是「下一个更大元素 I」LeetCode 496的镜像版本——把「更大」换成「更小」方向、比较符做相应调整即可。需要注意的是栈内弹出条件使用而非这样相同值的元素会被一侧归并保证每个区间的长度覆盖「并列最小值」的情况区间不重不漏地覆盖所有子数组。四种语言的完整实现Python3class Solution: def validSubarraySize(self, nums: List[int], threshold: int) - int: n len(nums) left, st [-1] * n, [] # left[i] 为左侧小于 nums[i] 的最近元素位置不存在时为 -1 for i, v in enumerate(nums): while st and nums[st[-1]] v: # 弹出 v 的保证栈顶是 v 的 st.pop() if st: left[i] st[-1] st.append(i) right, st [n] * n, [] # right[i] 为右侧小于 nums[i] 的最近元素位置不存在时为 n for i in range(n - 1, -1, -1): while st and nums[st[-1]] nums[i]: st.pop() if st: right[i] st[-1] st.append(i) for num, l, r in zip(nums, left, right): k r - l - 1 # 以 num 为最小值的最大区间长度 if num threshold // k: return k return -1Javaclass Solution { public int validSubarraySize(int[] nums, int threshold) { var n nums.length; var left new int[n]; // left[i] 为左侧小于 nums[i] 的最近元素位置不存在时为 -1 var st new ArrayDequeInteger(); for (var i 0; i n; i) { while (!st.isEmpty() nums[st.peek()] nums[i]) st.pop(); left[i] st.isEmpty() ? -1 : st.peek(); st.push(i); } var right new int[n]; // right[i] 为右侧小于 nums[i] 的最近元素位置不存在时为 n st new ArrayDeque(); for (var i n - 1; i 0; i--) { while (!st.isEmpty() nums[st.peek()] nums[i]) st.pop(); right[i] st.isEmpty() ? n : st.peek(); st.push(i); } for (var i 0; i n; i) { var k right[i] - left[i] - 1; if (nums[i] threshold / k) return k; } return -1; } }Cclass Solution { public: int validSubarraySize(vectorint nums, int threshold) { int n nums.size(); int left[n]; // left[i] 为左侧小于 nums[i] 的最近元素位置不存在时为 -1 stackint s; for (int i 0; i n; i) { while (!s.empty() nums[s.top()] nums[i]) s.pop(); left[i] s.empty() ? -1 : s.top(); s.push(i); } int right[n]; // right[i] 为右侧小于 nums[i] 的最近元素位置不存在时为 n s stackint(); for (int i n - 1; i 0; --i) { while (!s.empty() nums[s.top()] nums[i]) s.pop(); right[i] s.empty() ? n : s.top(); s.push(i); } for (int i 0; i n; i) { int k right[i] - left[i] - 1; if (nums[i] threshold / k) return k; } return -1; } };Gofunc validSubarraySize(nums []int, threshold int) int { n : len(nums) left : make([]int, n) // left[i] 为左侧小于 nums[i] 的最近元素位置不存在时为 -1 st : []int{-1} // 栈底哨兵保证栈永不为空left[i] 直接取栈顶 for i, v : range nums { for len(st) 1 nums[st[len(st)-1]] v { st st[:len(st)-1] // 弹出 v 的下标 } left[i] st[len(st)-1] st append(st, i) } right : make([]int, n) // right[i] 为右侧小于 nums[i] 的最近元素位置不存在时为 n st []int{n} // 哨兵换成 n for i : n - 1; i 0; i-- { for len(st) 1 nums[st[len(st)-1]] nums[i] { st st[:len(st)-1] } right[i] st[len(st)-1] st append(st, i) } for i, num : range nums { k : right[i] - left[i] - 1 if num threshold/k { return k } } return -1 }仓库模板里的单调栈上面的 Go 写法正是仓库 d.go 中validSubarraySize的实现。它使用了一个非常实用的模板技巧把哨兵-1和n直接压入栈底这样循环中栈永远不为空left[i]/right[i]可以直接取栈顶省去判空分支。该技巧在模板库 monotone_stack.go 中有完整的套路化演示其「山峰观景」的直觉解释如下把数组想象成一列山峰站在a[i]的山顶仰望两侧更高的山峰是看不到高山背后的矮山的。如果一座山无法看到那么在后续遍历中就永远无法看到。因此用一个底大顶小的单调栈入栈时不断弹出栈顶直到栈顶比当前元素大——被弹出的元素就是被当前元素挡住的、永远无法再看到的山。在本题中比较符号换成即可把「严格小于」的最近边界求出。此外monotone_stack.go 还示范了基于left/right的「贡献法」扩展cnt : (i - l) * (r - i)同一个左右边界数组既能算「以某值为最小值的区间数」也能像本题这样算「最大区间长度」一鱼两吃。复杂度分析时间复杂度$\mathcal{O}(n)$。每个元素至多入栈出栈各一次两次线性扫描加一次线性判断。空间复杂度$\mathcal{O}(n)$。left、right数组与单调栈。仓库级验证测试用例与评测框架算法正确性不仅要有推导还要有可复现的验证。仓库中每题目录的标准结构是xxx.go实现xxx_test.go测试入口xxx.txt用例数据本题的用例文件为 d.txt[1,3,4,3,1] 6 3 [6,5,6,5,8] 7 1即两组用例nums[1,3,4,3,1], threshold6期望输出3子数组[3,4,3]最小值 33 6/3 2nums[6,5,6,5,8], threshold7期望输出1。测试入口 d_test.go 通过仓库自研的测试工具读取用例文件并自动断言func Test_d(t *testing.T) { targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithFile(t, validSubarraySize, d.txt, targetCaseNum); err ! nil { t.Fatal(err) } }其底层实现RunLeetCodeFuncWithFile位于 leetcode/testutil/leetcode.go它读取.txt文件按函数签名输入参数个数 返回值个数自动切分每组用例再通过反射调用被测函数并比对期望输出把targetCaseNum设为-1或正整数时还可以只跑指定用例、失败时定位具体输入。这意味着仓库内两种解法并查集版validSubarraySize2与单调栈版validSubarraySize都可以直接替换到测试入口中做交叉验证——同一个数据文件两套算法必须给出完全一致的答案。两种方法对比与延伸维度方法一并查集方法二单调栈核心思路值从大到小激活连通块长度即k每个元素当最小值求最大区间依赖的数据结构并查集 排序单调栈时间复杂度$\mathcal{O}(n\log n)$排序为瓶颈$\mathcal{O}(n)$空间复杂度$\mathcal{O}(n)$$\mathcal{O}(n)$关键技巧离线按值激活、路径压缩、链长sz维护哨兵入栈简化判空、处理并列最小值从竞赛实用角度看单调栈解法是「求每个元素作为最值时的最大区间」这一模板题的直接套用编码量小、常数优推荐优先掌握并查集解法的价值在于示范了一种更通用的思维范式——当答案与「阈值/最值」强相关时按值离线排序 并查集动态维护连通信息往往能化繁为简该范式在按阈值离线处理区间问题例如最小生成树的 Kruskal 思想、按边权从小到大合并连通块中反复出现模板库 union_find.go 头部就给出了大量同类练习的题单索引。两道值得用同类手法练习的题目LeetCode 907子数组的最小值之和单调栈求左右边界 贡献法是本题方法二的直接姊妹题LeetCode 1856子数组最小乘积的最大值同样是「以最小值为核心」的区间枚举对理解「边界确定后区间唯一」的单调栈性质很有帮助。如果你需要系统训练这类套路仓库题解文档末尾的分类题单如单调栈题单、常用数据结构题单按「滑动窗口 / 二分 / 单调栈 / 图论 / DP / 并查集、树状数组、线段树」等主题做了完整归类可以直接作为刷题路线图使用仓库根目录的 leetcode/problems 目录则存放了全部 LeetCode 题解文件可随时按题号检索对照学习。小结LeetCode 2334 是一道典型的「最小值为锚点 区间长度最大化」的题目两道解法的对比清晰地展示了同一问题在两种数据结构视角下的不同面貌并查集视角按值从大到小激活用连通块大小天然承载「以当前值为最小值的最大区间长度」复杂度由排序主导单调栈视角一次性算出每个元素左右两侧最近更小位置区间长度即时可得线性完成全部计算。在 codeforces-go 仓库中两道解法均以可运行、可测试的 Go 源码存在d.go并通过 d_test.go d.txt 实现用例驱动的自动化验证其背后的通用套路——单调栈求边界、并查集离线合并——则沉淀在 monotone_stack.go 与 union_find.go 两个模板文件中可作为你后续参赛与刷题的即取即用工具。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 单调栈专题双单调栈求「下下个更大元素」——LeetCode 2454《下一个更大元素 IV》题解精讲codeforces go 单调栈专题双单调栈求「下下个更大元素」——LeetCode 2454《下一个更大元素 IV》题解精讲 本篇以算法竞赛模板库 cod科学计算下一个更大元素 ILeetCode 496单调栈全解右到左/左到右双写法与 codeforces-go 模板实践下一个更大元素 ILeetCode 496单调栈全解右到左/左到右双写法与 codeforces go 模板实践 本文以算法竞赛模板库 codeforce科学计算codeforces-go 竞赛模板库实战并查集倒序合并求解「删除元素后的最大子段和」codeforces go 竞赛模板库实战并查集倒序合并求解「删除元素后的最大子段和」 本文基于 codeforces go 仓库中 LeetCode 第 8科学计算上一篇Boot2Docker资源占用测试轻量级Linux的性能优势验证下一篇如何快速部署faster-whisper面向初学者的完整语音识别指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考