2026-08-15：删除元素后最大固定点数目。用go语言，给定一个整数数组 nums，你可以从中删除任意个元素（也可以不删）。删除后，剩下的元

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使用了一个经典技巧：

1. 1. 按第一维x升序排列。

2. 2. 如果第一维相同，按第二维i - x降序排列（代码中用b[1] - a[1]）。

这样排序的目的：

• • 按x升序，保证我们在处理时，固定点下标是递增的。

• • 相同x时降序，是为了防止在同一个新下标位置重复选择多个元素，因为按降序处理时，较大的删除数会先被处理，从而不会错误地让两个相同x的元素都进入 LIS。

排序后的数组，实际上我们关心第二维i - x能否构成一个严格递增的序列。

为什么？

• • 如果两个固定点分别位于原下标i1, i2，新下标x1, x2，并且x1 < x2。

• • 那么它们前面删除的元素个数分别是i1 - x1和i2 - x2。

• • 因为删除操作是全局的，若前一个固定点保留，后面固定点要想同时保留，必须保证后面的删除数大于前面的（因为越靠后的元素，要向前移动，需要的删除数也越多，并且这个删除数是递增的）。

所以我们需要找第二维的最长严格递增子序列（这里允许相邻相等，但排序时已经用降序避免同 x 的冲突，所以实际上用h+1来允许相等）。

sort.SearchInts(g, h+1)：

• • 用二分查找在g中找第一个 >=h+1的位置。

• • 相当于找第一个大于h的位置（允许相等情况下的处理）。

• • 如果找到就替换，否则追加，这样g的长度就是最长递增子序列的长度。

len(g)就是最多可以获得的固定点数量。

对于例子nums = [0, 2, 1]：

• • 原数组：

• • • i=0, x=0 => 0 >= 0 => [0, 0]

  • • i=1, x=2 => 1 >= 2? 否，跳过

  • • i=2, x=1 => 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 辅助数组g：O(n)

整体：O(n)

Go完整代码如下：

package main

 import (
    "cmp"
    "fmt"
    "slices"
    "sort"
)

 func maxEnvelopes(envelopes [][2]int) int {
    slices.SortFunc(envelopes, func(a, b [2]int) int {
        return cmp.Or(a[0]-b[0], b[1]-a[1])
    })

     g := []int{}
    for _, e := range envelopes {
        h := e[1]
        j := sort.SearchInts(g, h+1) // 允许 LIS 相邻元素相等
        if j < len(g) {
            g[j] = h
        } else {
            g = append(g, h)
        }
    }
    return len(g)
}

 func maxFixedPoints(nums []int) int {
    a := [][2]int{}
    for i, x := range nums {
        if i >= x {
            a = append(a, [2]int{x, i - x})
        }
    }
    return maxEnvelopes(a)
}

 func main() {
    nums := []int{0, 2, 1}
    result := maxFixedPoints(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List
from bisect import bisect_left

 def maxEnvelopes(envelopes: List[List[int]]) -> int:
    # 按宽度升序，宽度相同时按高度降序
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    g = []
    for _, h in envelopes:
        # 允许 LIS 相邻元素相等（通过 h+1 来插入位置）
        j = bisect_left(g, h + 1)
        if j < len(g):
            g[j] = h
        else:
            g.append(h)
    return len(g)

 def maxFixedPoints(nums: List[int]) -> int:
    a = []
    for i, x in enumerate(nums):
        if i >= x:
            a.append([x, i - x])
    return maxEnvelopes(a)

 if __name__ == "__main__":
    nums = [0, 2, 1]
    result = maxFixedPoints(nums)
    print(result)

C++完整代码如下：

  

    


 using namespace std;

 int maxEnvelopes(vector 
 
 int 
 >>& envelopes) { 
 
 
      
 // 按宽度升序，宽度相同时按高度降序 
 
 
     sort(envelopes.begin(), envelopes.end(), 
 
 
          []( 
 const 
  vector< 
 int 
 >& a,  
 const 
  vector< 
 int 
 >& b) { 
 
 
               
 if 
  (a[ 
 0 
 ] != b[ 
 0 
 ])  
 return 
  a[ 
 0 
 ] < b[ 
 0 
 ]; 
 
 
               
 return 
  a[ 
 1 
 ] > b[ 
 1 
 ]; 
 
 
          }); 
 
 
 
 
     vector< 
 int 
 > g; 
 
 
      
 for 
  ( 
 const 
  auto& e : envelopes) { 
 
 
          
 int 
  h = e[ 
 1 
 ]; 
 
 
          
 // 允许 LIS 相邻元素相等（通过 h+1 来插入位置） 
 
 
         auto it = lower_bound(g.begin(), g.end(), h +  
 1 
 ); 
 
 
          
 if 
  (it != g.end()) { 
 
 
             *it = h; 
 
 
         }  
 else 
  { 
 
 
             g.push_back(h); 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  g.size(); 
 
 
 } 
 
 
 
 
 int 
  maxFixedPoints(vector< 
 int 
 >& nums) { 
 
 
     vector 
 
 int 
 >> a; 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < nums.size(); i++) { 
 
 
          
 if 
  (i >= nums[i]) { 
 
 
             a.push_back({nums[i], i - nums[i]}); 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  maxEnvelopes(a); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > nums = { 
 0 
 ,  
 2 
 ,  
 1 
 }; 
 
 
      
 int 
  result = maxFixedPoints(nums); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。