【算法详解】删除元素后最大固定点数目（二维偏序LIS+CDQ分治 多解法超详解析）

【算法详解】删除元素后最大固定点数目（二维偏序LIS+CDQ分治 多解法超详解析）

目录

• 1. 题目描述

• 2. 核心问题分析

• 3. 暴力搜索与基础动态规划

  • 3.1 回溯法思路

  • 3.2 动态规划 O(n²) 解法

• 4. 优化：转化为二维偏序 LIS

  • 4.1 二维偏序模型

  • 4.2 CDQ 分治优化 O(n log² n)

  • 4.3 完整代码实现

  • 4.4 复杂度分析

• 5. 拓展：更多优化思路

• 6. 总结

1. 题目描述

给你一个整数数组nums。如果nums\[i\] == i，则位置i被称为固定点。

允许你从数组中删除任意数量的元素（包括零个）。在每次删除后，剩余元素向左移动，并且下标从0开始重新分配。

返回一个整数，表示在执行任意次数的删除操作后，可以获得的最大固定点数量。

示例演示

示例 1：

输入： nums = [0,2,1] 输出： 2 解释： 删除 nums[1] = 2。数组变为 [0, 1]。 现在，nums[0] = 0 且 nums[1] = 1，因此两个下标都是固定点。 因此，答案为 2。

示例 2：

输入： nums = [3,1,2] 输出： 2 解释： 不删除任何元素。数组保持为 [3, 1, 2]。 此时，nums[1] = 1 且 nums[2] = 2，因此这些下标是固定点。 因此，答案为 2。

示例 3：

输入： nums = [1,0,1,2] 输出： 3 解释： 删除 nums[0] = 1。数组变为 [0, 1, 2]。 现在，nums[0] = 0，nums[1] = 1，且 nums[2] = 2，因此所有下标都是固定点。 因此，答案为 3。

题目提示

• 1 \<= nums\.length \<= 10^5

• 0 \<= nums\[i\] \<= 10^5

2. 核心问题分析

删除数组元素的操作，本质等价于：从原数组中挑选一个保持原有相对顺序的子序列保留，剩余元素直接删除。保留后的子序列会重新从0分配连续下标。

我们的目标：让新数组中新下标 == 元素值的数量尽可能多。

数学模型推导

假设我们从原数组中选出一组递增下标序列：i₁ \< i₂ \< \.\.\. \< iₖ，作为保留元素。

在新数组中：第t个元素（从1开始计数）的新下标为t\-1。

若该元素为固定点，则必须满足：

n u m s [ i t ] = t − 1 nums[i_t] = t-1nums[it​]=t−1

基于该等式可以推导出核心约束条件：

1. 可行性前置条件：0 ≤ n u m s [ i ] ≤ i 0 \le nums[i] \le i0≤nums[i]≤i。如果nums\[i\] \> i，无论怎么删除前面元素，该元素的新下标一定小于原值，永远无法成为固定点，直接筛除。

2. 值单调递增：被选中的固定点元素值nums\[i\]必须严格递增。

3. 差值非递减：定义y i = i − n u m s [ i ] y_i = i - nums[i]yi​=i−nums[i]，合法序列必须满足y yy非递减。

问题最终转化

筛选出所有满足0 ≤ n u m s [ i ] ≤ i 0 \le nums[i] \le i0≤nums[i]≤i的下标，在其中寻找最长子序列，满足：

x j < x k , y j ≤ y k ( j < k ) x_j < x_k,\; y_j \le y_k \;\; (j<k)xj​<xk​,yj​≤yk​(j<k)

其中：x i = n u m s [ i ] , y i = i − n u m s [ i ] x_i = nums[i],\; y_i = i-nums[i]xi​=nums[i],yi​=i−nums[i]

这是经典的**二维偏序最长上升子序列(LIS)**问题。

3. 暴力搜索与基础动态规划

3.1 回溯法思路

最朴素的暴力思路：枚举数组所有子序列，对每个子序列重构新数组，统计固定点数量，记录最大值。

该思路逻辑完全贴合题意，适合新手理解题目本质，但时间复杂度为O ( 2 n ) O(2^n)O(2n)，仅适用于n \< 20的极小数据，无法通过题目大数据。

回溯完整代码（仅学习用）

classSolution:defmaxFixedPoints(self,nums:list[int])->int:# ©leetcoden=len(nums)max_cnt=0defbacktrack(idx,select):nonlocalmax_cntifidx==n:# 统计当前选中子序列的固定点数量cnt=0fornew_idx,valinenumerate(select):ifval==new_idx:cnt+=1max_cnt=max(max_cnt,cnt)return# 不选当前元素backtrack(idx+1,select)# 选当前元素select.append(nums[idx])backtrack(idx+1,select)select.pop()backtrack(0,[])returnmax_cnt

3.2 动态规划 O(n²) 解法

基于二维偏序模型，设计基础动态规划解法，消除暴力枚举子集的指数复杂度。

状态定义

dp\[i\]：以第i个候选元素作为末尾固定点的最长合法序列长度。

初始值：所有dp\[i\] = 1（单个元素自成序列）。

状态转移方程

对于每个i，遍历所有j \< i：

若满足x j < x i , y j ≤ y i x_j < x_i,\; y_j \le y_ixj​<xi​,yj​≤yi​：

d p [ i ] = m a x ( d p [ i ] , d p [ j ] + 1 ) dp[i] = max(dp[i], dp[j]+1)dp[i]=max(dp[i],dp[j]+1)

完整 O(n²) 代码

classSolution:defmaxFixedPoints(self,nums:list[int])->int:# ©leetcoden=len(nums)# 筛选合法候选元素cand=[]foriinrange(n):if0<=nums[i]<=i:cand.append((nums[i],i-nums[i]))m=len(cand)ifm==0:return0dp=[1]*m ans=1foriinrange(m):x_i,y_i=cand[i]forjinrange(i):x_j,y_j=cand[j]# 满足二维偏序条件ifx_j<x_iandy_j<=y_i:dp[i]=max(dp[i],dp[j]+1)ans=max(ans,dp[i])returnans

复杂度分析

• 时间复杂度：O ( n 2 ) O(n^2)O(n2)，双重循环遍历所有候选对

• 空间复杂度：O ( n ) O(n)O(n)，存储候选数组与dp数组

该解法可以通过小规模数据，但面对n = 10 5 n=10^5n=105会超时，必须进一步优化。

4. 优化：转化为二维偏序 LIS

4.1 二维偏序模型

常规一维LIS可以通过贪心+二分优化至O ( n log ⁡ n ) O(n\log n)O(nlogn)，但本题是二维约束：

序列需要同时满足：x严格递增、y非递减，且必须保留原数组下标顺序。

这类带顺序约束的二维偏序DP问题，最优离线解法为CDQ分治，可将复杂度优化至O ( n log ⁡ 2 n ) O(n\log^2 n)O(nlog2n)，完全适配 1e5 数据。

4.2 CDQ 分治优化 O(n log² n)

算法核心思想

CDQ分治核心：分而治之，先处理左区间，用左区间更新右区间，最后处理右区间。天然保证原数组下标有序，只需处理二维偏序条件。

1. 将候选数组划分为左右两个区间

2. 递归求解左区间的最优dp值

3. 按y升序合并左右区间，利用树状数组维护左区间的最大值，快速更新右区间dp

4. 递归求解右区间

关键预处理

• 离散化：x值域 0~1e5，压缩映射为树状数组下标

• 可回撤树状数组：维护前缀最大值，支持快速清空，适配分治多层递归

4.3 完整代码实现

classSolution:defmaxFixedPoints(self,nums:list[int])->int:# ©leetcoden=len(nums)# 筛选合法候选：0 <= nums[i] <= icand=[]foridxinrange(n):val=nums[idx]if0<=val<=idx:x=val y=idx-val cand.append((idx,x,y))m=len(cand)ifm==0:return0# dp[i]: 以第i个候选结尾的最长合法序列长度dp=[1]*m# 离散化 x 值，压缩值域x_list=sorted({item[1]foritemincand})x_rank={v:i+1fori,vinenumerate(x_list)}max_rank=len(x_list)# 可回撤最大值树状数组classMaxBIT:def__init__(self,size):self.size=size self.tree=[0]*(self.size+2)self.history=[]defupdate(self,pos,val):# 更新单点最大值whilepos<=self.size:ifself.tree[pos]<val:self.history.append(pos)self.tree[pos]=valelse:breakpos+=pos&-posdefquery(self,pos):# 查询[1,pos]最大值res=0whilepos>0:ifself.tree[pos]>res:res=self.tree[pos]pos-=pos&-posreturnresdefrollback(self):# 回撤本次所有修改，不影响上层递归forpinself.history:self.tree[p]=0self.history.clear()bit=MaxBIT(max_rank)# CDQ分治主体defcdq(l,r):ifl>=r:returnmid=(l+r)//2# 先处理左区间内部cdq(l,mid)# 合并左右，按y升序、原下标升序排序temp=[]foriinrange(l,r+1):_,x,y=cand[i]temp.append((y,i,x))temp.sort(key=lambdax:(x[0],x[1]))# 左区间更新右区间fory_val,idx,x_valintemp:ifidx<=mid:# 左区间元素，插入BITrk=x_rank[x_val]bit.update(rk,dp[idx])else:# 右区间元素，查询更新rk=x_rank[x_val]-1ifrk>=1:best=bit.query(rk)ifbest+1>dp[idx]:dp[idx]=best+1# 回撤树状数组bit.rollback()# 处理右区间内部cdq(mid+1,r)cdq(0,m-1)returnmax(dp)

测试代码

if__name__=="__main__":sol=Solution()print(sol.maxFixedPoints([0,2,1]))# 2print(sol.maxFixedPoints([3,1,2]))# 2print(sol.maxFixedPoints([1,0,1,2]))# 3

4.4 复杂度分析

• 时间复杂度：O ( n log ⁡ 2 n ) O(n\log^2 n)O(nlog2n)。分治递归深度O ( log ⁡ n ) O(\log n)O(logn)，每层排序+树状数组操作O ( n log ⁡ n ) O(n\log n)O(nlogn)。

• 空间复杂度：O ( n ) O(n)O(n)，候选数组、dp数组、树状数组均为线性空间。

该解法可完美通过10 5 10^5105大数据测试，是本题Python最优解法。

5. 拓展：更多优化思路

5.1 二维树状数组（2D BIT）

直接对y和x建立二维最大值树状数组，遍历数组直接DP转移，无需分治。复杂度同样O ( n log ⁡ 2 n ) O(n\log^2 n)O(nlog2n)，但Python中二位数组常数极大，容易超时，C++更推荐。

5.2 离线排序贪心优化

若将所有候选按y升序、x升序排序，问题退化为一维LIS问题。但该方法会破坏原数组下标顺序，仅适用于无顺序约束的二维偏序，本题不可直接使用。

5.3 单调队列优化

由于本题是二维约束，无法使用传统一维LIS的单调队列贪心优化，是本题的核心难点。

6. 总结

1. 本题核心难点：将删除子序列问题数学建模为二维偏序最长子序列问题，是算法转化思维的经典考题。

2. 暴力回溯、O(n²)DP仅适合逻辑学习，无法应对大数据。

3. CDQ分治是Python解决二维偏序DP的最优方案，复杂度O ( n log ⁡ 2 n ) O(n\log^2 n)O(nlog2n)，适配题目数据上限。

4. 本题模型可通用推广：所有「删除元素重排下标、求最值」的问题，均可通过原值\-下标转化为偏序LIS问题。