干货版《算法导论》12：双向链表优化与拆砖问题双解法

前言

算法之学，穷数据结构之妙，探时空复杂度之规。或借链表以序存数据，或凭指针以优化寻址；或借寓言包装数理，剥浮华而露内核。本篇拆解两道经典算法作业真题，其一为有序集合绑定指针优化双向链表移位操作，其二为披着野狼拆屋外衣的数组统计问题，一文尽述二分寻址、双指针滑动两大常用算法思想，附原理图文、C++ 落地源码，厘清时空复杂度优化思路。

Bilibili 同步视频

干货版《算法导论》12：双向链表优化与拆砖问题双解法

骈句开篇：
链表存序，困于线性遍历之迟；索引附针，巧取对数寻址之捷。
砖屋列阵，故事掩数组真意；双指同巡，线性遍历破繁难。

一、有序数组 + 指针优化双向链表移位算法

1.1 原始痛点：原生双向链表的短板

双向链表天然优势在于节点插入、删除仅需修改邻域指针，O (1) 完成局部改链，却有致命缺陷：若需随机定位指定节点，只能从头逐个遍历，最坏遍历全表，时间复杂度O ( N ) O(N)O(N)。
原题需求：给定若干文档编号以双向链表有序存储，实现moveBelow(x,y)操作：将节点 x 从原位置摘除，接入 y 节点后方，要求单次操作整体复杂度控制在O ( l o g N ) O(logN)O(logN)。
若仅依靠裸链表，查找 x、y 两个目标节点便耗时O ( N ) O(N)O(N)，无法满足题目性能约束。

【原生链表结构文本示意图】 裸双向链表： 1 <-> 5 <-> 3 <-> 2 <->7 无辅助索引，查找3：从头1→5→3，遍历3次 O(N)

1.2 优化思路：有序容器绑定链表节点指针

破局之策，有序集合存主键 + 链表节点指针，以空间换时间。

• 有序数组 / 平衡树存储所有文档主键，依托二分查找O ( l o g N ) O(logN)O(logN)快速锁定目标键；

• 每个键附属一块指针，直接指向双向链表内真实节点，无需遍历链表寻址。

【优化后整体架构文本示意图】 有序索引数组【键+指针】： [1(→链表1节点), 2(→链表2节点),3(→链表3节点),5(→链表5节点),7(→链表7节点)] 双向链表：1 <->5 <->3 <->2 <->7 指针特性：删除链表中3节点，其余所有索引内指针不受改动，永久有效

骈文注解：
键入有序之阵，二分寻位须臾；针连链表之身，定点改链瞬息。删一节点而全索引无恙，改一处链路而主键序如常。

1.3 moveBelow (x,y) 三步走实现逻辑

整项操作拆解为三大步骤，分步拆解复杂度：

1. 步骤 1：二分索引找 x、y：在有序索引容器二分查找 key=x、key=y，取出二者绑定的链表指针，O ( l o g N ) O(logN)O(logN)；

2. 步骤 2：链表摘除 x 节点：利用双向链表前驱、后继指针，断开 x 与前后节点关联，局部指针修改O ( 1 ) O(1)O(1)；

3. 步骤 3：x 接入 y 尾部：修改 y 与 y 原后继的指针，把 x 插入 y 之后，局部指针重定向O ( 1 ) O(1)O(1)。

总耗时：O ( l o g N ) + O ( 1 ) + O ( 1 ) = O ( l o g N ) O(logN)+O(1)+O(1)=O(logN)O(logN)+O(1)+O(1)=O(logN)，完美匹配题目性能需求。

补充关键细节：moveBelow 仅调整链表节点排布顺序，所有文档主键无新增、无删减，有序索引数组内容完全不需要改动，省去索引同步开销。

1.4 C++ 完整实现代码

依托 STLvector做有序索引，自定义双向链表结构体，指针存储链表节点地址：

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;// 双向链表节点结构体structListNode{intkey;ListNode*prev;ListNode*next;ListNode(intk):key(k),prev(nullptr),next(nullptr){}};// 索引单元：存储键+对应链表节点指针structIndexItem{intval;ListNode*ptr;// 重载小于号，用于二分查找booloperator<(constint&target)const{returnval<target;}};vector<IndexItem>sortedIndex;// 全局有序索引数组// 二分查找，返回对应链表节点指针ListNode*findNode(inttargetKey){autopos=lower_bound(sortedIndex.begin(),sortedIndex.end(),targetKey);returnpos->ptr;}// 将x移动至y的后面voidmoveBelow(intx,inty){ListNode*xNode=findNode(x);ListNode*yNode=findNode(y);// 1.摘除x节点ListNode*preX=xNode->prev;ListNode*nxtX=xNode->next;if(preX)preX->next=nxtX;if(nxtX)nxtX->prev=preX;// 2.x接入y之后ListNode*nxtY=yNode->next;yNode->next=xNode;xNode->prev=yNode;xNode->next=nxtY;if(nxtY)nxtY->prev=xNode;}intmain(){// 初始化链表：1<->5<->3<->2<->7ListNode*n1=newListNode(1),*n5=newListNode(5),*n3=newListNode(3);ListNode*n2=newListNode(2),*n7=newListNode(7);n1->next=n5;n5->prev=n1;n5->next=n3;n3->prev=n5;n3->next=n2;n2->prev=n3;n2->next=n7;n7->prev=n2;// 构建有序索引sortedIndex={{1,n1},{2,n2},{3,n3},{5,n5},{7,n7}};// 测试：把3挪到7后方moveBelow(3,7);cout<<"Finish Move Operation"<<endl;return0;}

1.5 落地答疑：Python 无原生指针如何模拟？

C++ 依托内存指针直接绑定节点地址，Python 无显性指针，实现思路为自定义对象实例，索引内存储对象引用，引用等价于指针功能，底层原理相通。

二、野狼拆砖屋问题：剥故事外壳，解数组统计内核

2.1 题意去魅：拨开童话伪装

原题以西方野狼、波特兰房屋、西风拆屋构建故事背景，本质是纯数组算法统计题：
给定一维数组a r r arrarr，代表自西向东排布房屋的砖块数量；选定下标i ii拆房，摧毁a r r [ i ] arr[i]arr[i]本身，同时摧毁右侧所有 ** 数值小于 arr [i]** 的元素，求每个下标对应可摧毁房屋总数，生成结果数组 ans。

示例数组：[34,57,70,19,48,2]

逐个演算： i=0(34): 右侧<34：19、2 → 合计3间(自身+2间)=3 i=1(57): 右侧<57：19、48、2 → 合计4间 i=2(70): 右侧全部小于70 → 合计4间

骈句：
野狼呼啸，本是童话虚妄；砖屋错落，实为数组列章。去风物之繁饰，留统计之本体。

2.2 特殊约束版：仅一处非特殊房屋，数组两段有序

特殊房屋定义：①最右侧末尾房屋；②右侧紧邻房屋砖块数≥当前房屋。
全数组仅有一间非特殊房屋 → 原数组天然被划分为左段单调递增、右段同样单调递增两个有序子数组。
例：[2,3,4,5,2,3,4]，仅下标 3 (5) 为非特殊点位，左[2,3,4,5]升序，右[2,3,4]升序。

数组分段文本图示 [左升序区｜分割点｜右升序区] 2 3 4 5 | 分割线 | 2 3 4 左：逐个变大；右：逐个变大

方案选型：双指针滑动算法（Two Finger），O ( N ) O(N)O(N)线性复杂度

普通暴力双循环统计复杂度O ( N 2 ) O(N^2)O(N2)，二分遍历优化O ( N l o g N ) O(NlogN)O(NlogN)，依托两段升序特性，同向双指针仅遍历一次全数组，O ( N ) O(N)O(N)最优解。
核心规律：左段数值自左向右逐步变大，能摧毁的右区间范围只会不断向右扩张，右指针j只递增、永不回退。

C++ 双指针实现代码

#include<iostream>#include<vector>usingnamespacestd;vector<int>calcDamage(vector<int>&arr,intsplitPos){vector<int>res(arr.size(),1);// 自身占1间intn=arr.size();intj=splitPos;// 右指针起始在分段位置// 遍历左升序区间for(inti=0;i<splitPos;i++){// j不断右移，找到首个>=arr[i]的位置while(j<n&&arr[j]<arr[i])j++;res[i]=j-i;}// 右升序区间，每个元素只能拆自身，ans全为1for(inti=splitPos;i<n;i++)res[i]=1;returnres;}intmain(){vector<int>arr={2,3,4,5,2,3,4};vector<int>ans=calcDamage(arr,4);for(autox:ans)cout<<x<<" ";return0;}

运行输出：7 6 5 4 1 1 1

2.3 无特殊约束通用版算法思路

若无 “仅一间特殊房屋” 前置条件，数组无序，无法使用双指针线性解法，可依托归并排序的分治思想，在归并过程统计右侧小于当前值的元素数量，整体复杂度O ( N l o g N ) O(NlogN)O(NlogN)，是此类逆序统计类问题的通用范式。

三、算法优化思想复盘总结

骈文小结：
其一，附针于索引，以二分破链表遍历之困，对数耗时，是空间换速率之典；
其二，双指同巡弋，借有序缩区间查找之繁，线性遍历，是规律破暴力之弊。

1. 索引 + 指针优化链表：遇到随机查找 + 局部增删场景，优先思考「辅助索引 + 实体指针 / 引用」，拆分查找与修改的复杂度，查找对数、改链常数；

2. 双指针滑动技巧：数组分段有序、单调性明确时，优先同向 / 对向双指针，规避嵌套循环，压至线性复杂度；

3. 算法剥壳思维：工程与习题常以业务、故事包装数理逻辑，解题首步剥离无效场景描述，提炼纯数学模型，是算法入门必备素养。

结语

算法研习，不在记代码之形，而在悟优化之理。链表附针，明索引优化之方；拆砖寻数，晓双指针妙用之法。举一反三，遇同类题目便可触类旁通，于笔试、工程开发皆大有裨益。