2026-08-15删除元素后最大固定点数目。用go语言给定一个整数数组 nums你可以从中删除任意个元素也可以不删。删除后剩下的元素会依次向左靠拢下标从 0 开始重新编号。如果某个位置上的元素值恰好等于它的新下标这个位置就称为“固定点”。请计算经过任意次删除操作后最多能得到多少个固定点。1 nums.length 100000。0 nums[i] 100000。输入 nums [0,2,1]。输出 2。解释删除 nums[1] 2。数组变为 [0, 1]。现在nums[0] 0 且 nums[1] 1因此两个下标都是固定点。因此答案为 2。题目来自力扣3920。大体步骤如下第一步理解问题转化题目要求我们删除任意个元素后让剩下的元素在重新编号后尽量多的位置满足“元素值 新下标”。你的代码没有直接去模拟删除而是做了一个数学建模。第二步构造候选点固定点可能的位置代码中的maxFixedPoints函数首先遍历原始数组nums对每个位置i和值x如果i x说明如果保留这个元素并且它最终被移到了某个位置有可能成为固定点。它保存一对值[x, i - x]。这里的含义是如果保留这个元素并且它最终成为固定点那么它新下标必须等于 x。这个元素原本在位置i如果它被移动到了下标x那么它前面需要删除的元素个数为i - x因为向前移动。所以[x, i - x]就代表了“这个元素如果要成为固定点需要的删除数量是i - x且它对应新下标x”。第三步排序二维偏序处理将这些候选点存入二维数组a然后交给maxEnvelopes处理。maxEnvelopes使用了一个经典技巧按第一维x升序排列。如果第一维相同按第二维i - x降序排列代码中用b[1] - a[1]。这样排序的目的按x升序保证我们在处理时固定点下标是递增的。相同x时降序是为了防止在同一个新下标位置重复选择多个元素因为按降序处理时较大的删除数会先被处理从而不会错误地让两个相同x的元素都进入 LIS。第四步最长递增子序列LIS处理排序后的数组实际上我们关心第二维i - x能否构成一个严格递增的序列。为什么如果两个固定点分别位于原下标i1, i2新下标x1, x2并且x1 x2。那么它们前面删除的元素个数分别是i1 - x1和i2 - x2。因为删除操作是全局的若前一个固定点保留后面固定点要想同时保留必须保证后面的删除数大于前面的因为越靠后的元素要向前移动需要的删除数也越多并且这个删除数是递增的。所以我们需要找第二维的最长严格递增子序列这里允许相邻相等但排序时已经用降序避免同 x 的冲突所以实际上用h1来允许相等。sort.SearchInts(g, h1)用二分查找在g中找第一个 h1的位置。相当于找第一个大于h的位置允许相等情况下的处理。如果找到就替换否则追加这样g的长度就是最长递增子序列的长度。第五步得到答案len(g)就是最多可以获得的固定点数量。对于例子nums [0, 2, 1]原数组i0, x0 0 0 [0, 0]i1, x2 1 2? 否跳过i2, x1 2 1 [1, 1]候选[[0,0], [1,1]]排序后[[0,0], [1,1]]LIS 长度 2输出 2正确。时间复杂度构造候选O(n)排序O(n log n)LIS 二分每个元素一次二分查找O(log n)总共 O(n log n)整体O(n log n)额外空间复杂度候选数组a最多 n 个元素O(n)LIS 辅助数组gO(n)整体O(n)Go完整代码如下packagemainimport(cmpfmtslicessort)funcmaxEnvelopes(envelopes[][2]int)int{slices.SortFunc(envelopes,func(a,b[2]int)int{returncmp.Or(a[0]-b[0],b[1]-a[1])})g:[]int{}for_,e:rangeenvelopes{h:e[1]j:sort.SearchInts(g,h1)// 允许 LIS 相邻元素相等ifjlen(g){g[j]h}else{gappend(g,h)}}returnlen(g)}funcmaxFixedPoints(nums[]int)int{a:[][2]int{}fori,x:rangenums{ifix{aappend(a,[2]int{x,i-x})}}returnmaxEnvelopes(a)}funcmain(){nums:[]int{0,2,1}result:maxFixedPoints(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListfrombisectimportbisect_leftdefmaxEnvelopes(envelopes:List[List[int]])-int:# 按宽度升序宽度相同时按高度降序envelopes.sort(keylambdax:(x[0],-x[1]))g[]for_,hinenvelopes:# 允许 LIS 相邻元素相等通过 h1 来插入位置jbisect_left(g,h1)ifjlen(g):g[j]helse:g.append(h)returnlen(g)defmaxFixedPoints(nums:List[int])-int:a[]fori,xinenumerate(nums):ifix:a.append([x,i-x])returnmaxEnvelopes(a)if__name____main__:nums[0,2,1]resultmaxFixedPoints(nums)print(result)C完整代码如下#includevector#includealgorithm#includeiostreamusingnamespacestd;intmaxEnvelopes(vectorvectorintenvelopes){// 按宽度升序宽度相同时按高度降序sort(envelopes.begin(),envelopes.end(),[](constvectorinta,constvectorintb){if(a[0]!b[0])returna[0]b[0];returna[1]b[1];});vectorintg;for(constautoe:envelopes){inthe[1];// 允许 LIS 相邻元素相等通过 h1 来插入位置autoitlower_bound(g.begin(),g.end(),h1);if(it!g.end()){*ith;}else{g.push_back(h);}}returng.size();}intmaxFixedPoints(vectorintnums){vectorvectorinta;for(inti0;inums.size();i){if(inums[i]){a.push_back({nums[i],i-nums[i]});}}returnmaxEnvelopes(a);}intmain(){vectorintnums{0,2,1};intresultmaxFixedPoints(nums);coutresultendl;return0;}