2026-08-08数组中的有效元素。用go语言给定一个整数序列。对于其中的任意一个数如果它比它左边出现过的所有数都大或者比它右边出现过的所有数都大那它就符合筛选条件。另外序列的第一个数和最后一个数无论大小都直接视为符合条件。最后按照这些数在原序列中的出现顺序将它们全部找出来。1 nums.length 100。1 nums[i] 100。输入 nums [1,2,4,2,3,2]。输出 [1,2,4,3,2]。解释nums[0] 和 nums[5] 始终有效。nums[1] 和 nums[2] 都严格大于其左侧的所有元素。nums[4] 严格大于其右侧的所有元素。因此答案为 [1, 2, 4, 3, 2]。题目来自力扣3912。该算法分两个主要阶段通过两次遍历和辅助标记数组找出所有符合“左侧最大”或“右侧最大”条件的有效元素。阶段一从右向左遍历标记右侧最大元素创建一个与输入数组nums等长的布尔数组rightValid用于记录每个位置的元素是否严格大于它右边的所有元素。初始时所有值均为假。设置一个变量mx表示当前已经扫描过的右侧部分的最大值。由于数组元素取值范围为 1~100将mx初始化为 0任何元素都大于 0这样可以正确处理数组最后一个元素。从最后一个元素开始逆序向前遍历数组取出当前元素x。若x严格大于mx则说明x大于它右侧所有已扫描元素即满足“严格大于右侧所有元素”的条件将rightValid[i]设为真否则设为假。然后用x更新mx使mx始终维护从当前位置到数组末尾的最大值。遍历结束后rightValid数组的每个位置都对应原数组元素标记了该元素是否比它右边的所有数都大。特别地最后一个元素右侧无元素其对应mx初始为 0因此一定会被标记为真符合题目“最后一个元素始终有效”的规则。阶段二从左向右遍历结合左侧条件和右侧标记收集结果重置mx为 0此时mx表示当前已扫描过的左侧部分的最大值。准备一个空的结果列表ans用于按序存放有效元素。从第一个元素开始顺序向前遍历数组取出当前元素x。判断条件若x严格大于mx则说明x大于它左侧所有已扫描元素即满足“严格大于左侧所有元素”若rightValid[i]为真则说明x满足“严格大于右侧所有元素”。这两个条件只要满足其一当前元素就是有效元素将其加入ans。无论是否加入结果都用x更新mx使mx始终维护从数组起始到当前位置的最大值。对于第一个元素因其左侧无元素mx初始为 0必然满足x mx因此一定会被加入结果符合“第一个元素始终有效”的规则。遍历完成后ans中即为所有有效元素且保持了原数组的出现顺序。时间复杂度分析算法包含两次独立的线性遍历从右向左遍历一次从左向右遍历一次每次仅包含常数时间的比较、赋值和更新操作。因此总的时间复杂度为O(n)其中 n 为数组长度。额外空间复杂度分析除了输入数组和最终返回的结果数组外算法额外分配了一个长度与输入相同的布尔数组rightValid用于存储每个位置的右侧最大标记。该数组占用 O(n) 空间。过程中仅使用了常数个辅助变量如mx、循环索引等因此总的额外空间复杂度为O(n)。如果严格将返回结果所用的空间不计入额外空间则依然为 O(n)。Go完整代码如下packagemainimport(fmtslices)funcfindValidElements(nums[]int)(ans[]int){// 标记严格大于其右侧所有元素的元素rightValid:make([]bool,len(nums))mx:0fori,x:rangeslices.Backward(nums){rightValid[i]xmx mxmax(mx,x)}mx0fori,x:rangenums{ifxmx||rightValid[i]{ansappend(ans,x)}mxmax(mx,x)}return}funcmain(){nums:[]int{1,2,4,2,3,2}result:findValidElements(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-deffindValidElements(nums):nlen(nums)rightValid[False]*n mx0foriinrange(n-1,-1,-1):xnums[i]rightValid[i]xmx mxmax(mx,x)mx0ans[]fori,xinenumerate(nums):ifxmxorrightValid[i]:ans.append(x)mxmax(mx,x)returnansif__name____main__:nums[1,2,4,2,3,2]resultfindValidElements(nums)print(result)C完整代码如下#includevector#includeiostream#includealgorithmstd::vectorintfindValidElements(conststd::vectorintnums){intnnums.size();if(n0)return{};// 标记严格大于其右侧所有元素的元素std::vectorboolrightValid(n,false);intmx0;for(intin-1;i0;--i){intxnums[i];rightValid[i](xmx);mxstd::max(mx,x);}// 根据左侧最大值和右侧标记收集有效元素std::vectorintans;mx0;for(inti0;in;i){intxnums[i];if(xmx||rightValid[i]){ans.push_back(x);}mxstd::max(mx,x);}returnans;}intmain(){std::vectorintnums{1,2,4,2,3,2};std::vectorintresultfindValidElements(nums);for(intx:result){std::coutx ;}std::coutstd::endl;return0;}