企业官网建设流程全解析

• 科学计算

本文以 codeforces-go 仓库中第 82 场 LeetCode 双周赛 D 题（LeetCode 2334，Subarray 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.md，Go 代码实现位于 d.go。

方法一：并查集——从大到小激活元素，用链长代表 k

解题思路的四个提示

原题解文档给出了四个层层递进的提示，这里逐一展开：

• 提示 1：数组中的元素越大越好，不妨从大往小考虑nums[i]。因为条件只关心「子数组的最小值」，最小值越大越容易满足要求，所以按元素值从大到小的顺序逐个"激活"位置是自然的切入点。
• 提示 2：子数组的长度k越大，threshold / k就越小，越能满足要求。这说明在固定最小值时，我们总是希望区间尽可能长。
• 提示 3：把考虑过的元素都串起来，这条链的长度就是k。当按值从大到小激活位置后，被激活的相邻位置会连成一整段，而每个当前被激活的元素所能构成的、以它为最小值的最大区间，正是它所在的连续激活段——段长即k。
• 提示 4：用并查集动态维护链长。遍历到nums[i]时，用并查集把i和i+1合并，即可把连续访问过的位置串成一条链，同时维护每条链的长度sz。

核心不变量

算法维护的关键不变量是：

当我们按值从大到小处理到某个元素num时，所有值大于等于num的位置都已被激活，并且已激活的相邻位置被并查集合并成若干连通块。对当前元素num而言，它所在连通块的大小sz，就是「以num为最小值」的最长连续区间长度k。

于是每次激活后只需检查num > threshold / sz是否成立（为避免浮点误差，写成整除/乘法形式），成立即返回sz。由于我们是按值从大到小处理的，第一个命中的k就是题目要找的答案。

四种语言的完整实现

Python3

class 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)), reverse=True): j = find(i + 1) # 找到 i+1 所在链的链头 fa[i] = j # 合并 i 和 i+1，让 i 指向右侧链头 sz[j] += sz[i] + 1 # 链长增加（sz[i] 是 i 左侧已合并的部分） if num > threshold // sz[j]: return sz[j] # 满足条件，返回链长 return -1

Java

class 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 和 i+1 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]; } }

C++

class Solution { public: int validSubarraySize(vector<int> &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)); function<int(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 和 i+1 sz[j] += sz[i] + 1; if (nums[i] > threshold / sz[j]) return sz[j]; } return -1; } };

Go

func 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, n+1) for i := range fa { fa[i] = i } sz := make([]int, n+1) 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 和 i+1 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数组各需n+1的空间。

仓库模板库 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）的镜像版本——把「更大」换成「更小」，方向、比较符做相应调整即可。

需要注意的是，栈内弹出条件使用>=（而非>），这样相同值的元素会被一侧归并，保证每个区间的长度覆盖「并列最小值」的情况，区间不重不漏地覆盖所有子数组。

四种语言的完整实现

Python3

class 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 -1

Java

class 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 ArrayDeque<Integer>(); 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; } }

C++

class Solution { public: int validSubarraySize(vector<int> &nums, int threshold) { int n = nums.size(); int left[n]; // left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1） stack<int> 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 = stack<int>(); 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; } };

Go

func 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], threshold=6期望输出3（子数组[3,4,3]，最小值 3，3 > 6/3 = 2）；nums=[6,5,6,5,8], threshold=7期望输出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）都可以直接替换到测试入口中做交叉验证——同一个数据文件，两套算法必须给出完全一致的答案。

两种方法对比与延伸

从竞赛实用角度看：单调栈解法是「求每个元素作为最值时的最大区间」这一模板题的直接套用，编码量小、常数优，推荐优先掌握；并查集解法的价值在于示范了一种更通用的思维范式——当答案与「阈值/最值」强相关时，按值离线排序 + 并查集动态维护连通信息往往能化繁为简，该范式在按阈值离线处理区间问题（例如最小生成树的 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 两个模板文件中，可作为你后续参赛与刷题的即取即用工具。

• 科学计算