第五章:双指针与区间扫描

枚举全部数对或全部连续区间常常需要平方时间。如果一次比较能排除一整批候选,就不必逐个访问它们。双指针利用有序性或窗口约束,让左右边界只向一个方向移动;本章重点说明每次移动舍弃了什么,以及为什么不会漏掉答案。

第二章已经用两个下标枚举过位置对,也用左右端点表示过连续区间。这里仍在考虑相同的候选对象,区别在于:一旦证明某些候选都不可能更好,就把它们整批排除。能否排除必须由当前比较得出,不能仅凭“用了两个下标”就断定算法正确。

本章的主要实现均为独立完整程序。阅读前需要掌握排序、区间端点和频次数组。同向双指针可以维护连续区间,但指针如何移动必须由题目的具体条件推出;固定长度区间的最值维护见第九章的单调队列。

1. 从一次比较排除一批数对

先做一个小任务:给定升序数组,判断是否存在两个不同位置,其数值之和等于 KK。本节练习格式为第一行 n,Kn,K,第二行 nn 个数,输出 YES 或 NO;规定 1≤n≤2×1051\le n\le2\times10^5,∣ai∣,∣K∣≤109|a_i|,|K|\le10^9。程序会先排序,因此输入不必已经有序。

直接枚举所有 i<ji<j,需要 O(n2)O(n^2) 次比较。排序后,令 l=1,r=nl=1,r=n,暂时只保留左右端点之间的元素。比较最小剩余值 ala_l 与最大剩余值 ara_r:

  • 若 al+ar<Ka_l+a_r<K,则 ala_l 与任意剩余元素的和都不超过 al+ara_l+a_r,全部偏小。所有使用位置 ll 的剩余候选都可以删除,让 ll 增加。
  • 若 al+ar>Ka_l+a_r>K,则 ara_r 与任意剩余元素的和都不小于 al+ara_l+a_r,全部偏大。所有使用位置 rr 的剩余候选都可以删除,让 rr 减少。
  • 若相等,已经找到两个不同位置,直接成功。

不是每次比较只排除刚刚试过的一对,而是排除所有含某一端点的候选。这正是从平方次比较降到线性次比较的原因。

用 [1,2,4,7,11][1,2,4,7,11]、K=10K=10 手算:

剩余下标 [l,r][l,r]两端和排除的候选下一步
[1,5][1,5]1+11=121+11=12所有含位置 55 的剩余数对r=4r=4
[1,4][1,4]1+7=81+7=8所有含位置 11 的剩余数对l=2l=2
[2,4][2,4]2+7=92+7=9所有含位置 22 的剩余数对l=3l=3
[3,4][3,4]4+7=114+7=11剩余的 (3,4)(3,4)r=3r=3,无解

数对候选矩阵:一次比较删除含某一端点的一整行或一整列候选

当 l=rl=r 时只剩一个位置,不能与自己配对,所以循环条件是 l<rl<r。全过程始终保持“尚未排除的解都在 [l,r][l,r] 中”。每次移动都有上述排除理由;区间不足两个位置时,全部候选已经排除,便可输出无解。

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
long long a[N];
int main(){
    int n;
    long long k;
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    int l=1,r=n;
    while(l<r){
        long long s=a[l]+a[r];
        if(s==k){puts("YES");return 0;}
        if(s<k)++l;
        else --r;
    }
    puts("NO");
}

数组排序耗时 O(nlog⁡n)O(n\log n)。扫描每轮让区间至少缩短一位,所以只有 O(n)O(n) 次移动;排序后的扫描只需常数额外空间。负数不影响这个证明,只要数组已经有序,两个端点比较的大小关系就成立。

这个程序只判断有没有解。若改为统计所有位置对,找到一对后立即返回会漏掉其他方案;第 3 节会专门处理重复值的计数。

2. 首尾双指针与最少分组

例题:NOIP 2007 普及组·纪念品分组。

简易题面:将全部纪念品分组,每组至多两件且价格和不超过 ww,求最少组数。

数据范围:1≤n≤3×1041\le n\le3\times10^4,80≤w≤20080\le w\le200,5≤pi≤w5\le p_i\le w。

直接枚举所有分组,需要尝试大量配对。先考虑最贵的纪念品:它必须被安排,而能与它同组的物品受剩余容量限制最多。把价格升序排列,令最便宜、最贵的剩余物品分别为 l,rl,r。

若两者价格和仍超过上限,rr 与其他物品也不可能同组,只能单独安排。若两者能够同组,则存在一个最优方案让它们配对:原方案中若 rr 与 xx 配对、ll 与 yy 配对,交换为 (l,r)(l,r)、(x,y)(x,y) 后,前一组合法,后一组满足 px+py≤px+pr≤wp_x+p_y\le p_x+p_r\le w。若其中一件原本单独成组,交换后也不会增加组数。因此可以固定这一选择,继续处理剩余物品。

把交换的特殊情况也展开。如果最便宜与最贵原本已经同组,保持原样即可;若都单独成组,合并只会减少组数;若一个单独、另一个有伙伴,重新把最便宜与最贵放在一组,把原伙伴单放,组数不增加。双方都有不同伙伴时才需要上述两组之间的交换。这样,任意最优方案都能改成采用当前选择的方案。

例如上限为 100100,价格为 20,30,70,8020,30,70,80,先取 20,8020,80,再取 30,7030,70,共两组。再看 20,50,80,9020,50,80,90:

尚未安排的价格两端和本轮安排累计组数
20,50,80,9020,50,80,901101109090 单独11
20,50,8020,50,8010010020,8020,80 同组22
5050不再配对5050 单独33

每轮删去的是已经有合理安排的物品,与上一节删去不可能的数对有所不同。这里还需要交换论证保证最少组数,这也是第八章贪心方法会继续讨论的证明方式。每组至多两件是论证的条件;允许三件时,不能直接沿用。

落实到本题,每轮都处理当前最贵的一件,并增加一组;若最便宜的一件可以与它配对,就一起取走。完整程序先读入上限 ww,再读件数 nn 和各件价格,排序后开始扫描;本题单价至多为 200200,两件之和至多为 400400,可用 int\texttt{int}。

#include <bits/stdc++.h>
using namespace std;
const int N=30010;
int a[N];
int main(){
    int n,w;
    cin>>w>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    sort(a+1,a+n+1);
    int l=1,r=n,ans=0;
    while(l<=r){
        if(l<r&&a[l]+a[r]<=w)++l;
        --r;
        ++ans;
    }
    cout<<ans<<'\n';
}

只剩一件时也必须增加一组,因此条件使用 l≤rl\le r;但不能把这件物品与自己配对,所以相加前另判 l<rl<r。排序与扫描合计为 O(nlog⁡n)O(n\log n),扫描额外空间为 O(1)O(1)。

3. 同向双指针

3.1 快慢指针去重

现在要求把数组中的不同数值升序输出。练习的输入为第一行 nn、第二行 nn 个整数,输出不同值个数和这些值;规定 1≤n≤2×1051\le n\le2\times10^5,元素在 int\texttt{int} 范围内。这里明确按数值去重,所以两个位置上的相同值只保留一次。

先排序,相同值就会相邻。让读取位置 ii 扫描全部输入,让写入位置 mm 记录已保留的长度。对于 [1,1,2,2,3][1,1,2,2,3]:

读取位置 ii读到的值是否写入保留部分
1111还没有值,写入[1][1]
2211与最后保留值相同[1][1]
3322不同,写到位置 22[1,2][1,2]
4422相同,跳过[1,2][1,2]
5533不同,写到位置 33[1,2,3][1,2,3]

第三轮把位置 22 改为 22,不会影响尚未读取的位置 4,54,5。写指针不会超过读指针,是可以原地压缩的原因。全局数组容量覆盖 n+1n+1,mm 初始为零。

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int m=0;
    for(int i=1;i<=n;++i){
        if(m==0||a[i]!=a[m])a[++m]=a[i];
    }
    printf("%d\n",m);
    for(int i=1;i<=m;++i)printf("%d%c",a[i],i==m?'\n':' ');
}

ii 扫描原序列,mm 指向已经保留的最后一个元素。

处理完位置 ii 后,前 mm 个元素恰好是原来前 ii 个元素的不同值,且依然有序。m≤im\le i,所以写入位置始终不超过已读位置。条件中的 m=0m=0 先处理“还没有保留元素”,此时不应该把 a[0]a[0] 当成有效值比较。

3.2 差值数对

本节使用自足练习“差值数对”。原资料中的校内题库链接需要内网访问,因此以下输入、输出和范围就是本节代码所依据的完整约定。相关公开练习见 A-B 数对,提交时应以对应站点题面为准。

简易题面:给定 nn 个非负整数和正整数 CC,统计满足 ai−aj=Ca_i-a_j=C 的有序位置对 (i,j)(i,j) 的数量。相同数值出现在不同位置时分别计数。

输入第一行是 n,Cn,C,第二行是 nn 个数,输出一个整数表示数对数量。数据范围:1≤n≤2×1051\le n\le2\times10^5,1≤C≤1091\le C\le10^9,0≤ai≤1090\le a_i\le10^9。

枚举两个位置需要 O(n2)O(n^2) 时间。排序后,依次固定较小值 aia_i,需要统计较大值 ai+Ca_i+C 出现多少次。用 ll 指向第一个不小于目标的位置,rr 指向第一个大于目标的位置,则相等值占据半开区间 [l,r)[l,r),贡献为 r−lr-l。

随着 ii 增大,目标 ai+Ca_i+C 不会减小。已经小于旧目标的位置也一定小于新目标,因此两个边界都不必回退。数组已经有序时,两个边界共移动至多 2n2n 次。

这里循环固定的是较小值所在的位置,最终形成的有序对却是“较大值位置在前、较小值位置在后”。排序改变了存储次序,但每个原位置仍对应一个元素,且答案只求数量,因此不需要恢复原下标。

用 [1,1,2,2,3][1,1,2,2,3]、C=1C=1 逐轮计算:

ii较小值目标值目标出现范围 [l,r)[l,r)增加数对
111122[3,5)[3,5)22
221122[3,5)[3,5)22
332233[5,6)[5,6)11
442233[5,6)[5,6)11
553344[6,6)[6,6)00

n+1n+1 表示已经走过数组末尾,不能再读取这个位置。没有目标时,两个边界相等,贡献为零。目标变大后,ll 可能越过原来的 rr;先让 r=max(r,l)\texttt{r=max(r,l)},再寻找新目标的结束位置,可以保持区间端点合法。

以下 aa 为全局整数数组,容量至少为 200010200010。目标值至多为 2×1092\times10^9,可用 int\texttt{int};数对数量可能超过 32 位整数范围,答案使用 long long\texttt{long long}。

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N];
int main(){
    int n,C;
    scanf("%d%d",&n,&C);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int l=1,r=1;
    long long ans=0;
    for(int i=1;i<=n;++i){
        int x=a[i]+C;
        while(l<=n&&a[l]<x)++l;
        r=max(r,l);
        while(r<=n&&a[r]==x)++r;
        ans+=r-l;
    }
    printf("%lld\n",ans);
}

表中两个值为 11 的位置都要分别贡献答案。重复值不能去重,否则会丢失位置对;目标不存在时,两条边界相等,本轮贡献为 00。

排序需要 O(nlog⁡n)O(n\log n) 时间,扫描需要 O(n)O(n) 时间。C>0C>0 保证目标严格大于当前值,不会把同一位置与自身配对。

如果将范围改为允许 C=0C=0,必须先问清位置对的含义。一个值出现 tt 次时:允许 i=ji=j 的有序对有 t2t^2 个;要求 i≠ji\ne j 的有序对有 t(t−1)t(t-1) 个;无序的不同位置对只有 t(t−1)/2t(t-1)/2 个。例如三个相同值分别产生 9,6,39,6,3 个答案。上面的代码直接用于 C=0C=0 会得到第一种结果。若任务要求第二种结果,可在每轮贡献中减一;若要求第三种,应按相等值分段统计,不能同时计算两个方向。本节主任务的 C>0C>0 条件正好避开了这些口径差异。

3.3 维护最短覆盖区间

例题:逛画展。

简易题面:寻找包含全部 mm 位画家作品的最短连续区间;并列时输出左端点最小的一组。

数据范围:1≤m≤20001\le m\le2000,m≤n≤106m\le n\le10^6,1≤ai≤m1\le a_i\le m,保证有解。

枚举左右端点,再逐幅检查画家是否齐全,会反复统计同一段作品。固定右端点时,可以复用上一个窗口的频次;左端只要还有同一画家的其他作品,就能删去一幅而不失去覆盖。

窗口是闭区间 [l,r][l,r]。cnt[v]cnt[v] 表示画家 vv 的作品在窗口中有几幅,kindkind 表示频次非零的画家数。右边加入一幅时,只有它的频次从零变成一,kindkind 才增加;从一变成二并没有增加新画家。

使用 [1,1,2,3,2,1][1,1,2,3,2,1]、m=3m=3,把每次加入和收缩写出来:

新右端 rr加入后及收缩动作最终窗口频次 (1,2,3)(1,2,3)是否更新答案
11加入 11[1,1][1,1](1,0,0)(1,0,0)尚不完整
22加入 11,删去旧的 11[2,2][2,2](1,0,0)(1,0,0)尚不完整
33加入 22[2,3][2,3](1,1,0)(1,1,0)尚不完整
44加入 33,左端只剩一个 11[2,4][2,4](1,1,1)(1,1,1)长度 33,记录
55加入 22,左端仍不可删[2,5][2,5](1,2,1)(1,2,1)长度 44,不更新
66加入 11,依次删去左侧 1,21,2[4,6][4,6](1,1,1)(1,1,1)同长,保留更早左端

覆盖窗口依次加入作品并删除重复的左端,kind 只统计非零频次

查看最后一轮静态图。图中绿色框是闭区间窗口,灰色框是暂不在窗口内的作品。

这里的收缩只删除频次大于一的左端,因此不会让某类画家从有变成无,kindkind 无须在收缩时减少。如果采用“完整就先记录,再强行删除一个左端”的另一种写法,则频次降到零时必须减少 kindkind;两种维护方式不能混用。

全局整数数组 a,cnta,cnt 分别保存作者和窗口频次,容量为 10000101000010、20102010,初始均为零。ans=n+1ans=n+1 表示还没找到完整窗口,x,yx,y 保存已找到的端点。原题保证有解,程序也约定无完整覆盖时输出 -1,便于将这个方法用于未保证有解的输入。

#include <bits/stdc++.h>
using namespace std;
const int N=1000010,M=2010;
int a[N],cnt[M];
int main(){
    int n,m,x=0,y=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    int l=1,kind=0,ans=n+1;
    for(int r=1;r<=n;++r){
        if(++cnt[a[r]]==1)++kind;
        while(cnt[a[l]]>1){
            --cnt[a[l]];
            ++l;
        }
        if(kind==m&&r-l+1<ans){
            ans=r-l+1;
            x=l;
            y=r;
        }
    }
    if(ans==n+1)puts("-1");
    else printf("%d %d\n",x,y);
}

例如作者序列 1,1,2,31,1,2,3,读到第四幅时,最左的一幅可以删除,得到 [2,4][2,4];再删就缺少画家 11。收缩结束后,左端对应的画家只剩一幅,继续右移就会缺失该画家。因此一旦窗口完整,它就是当前右端点对应的最短完整窗口。若某个最优窗口右端为 rr,程序处理到这个 rr 时得到的窗口不会更长,所以枚举全部右端点必然能找到全局最短答案。左右端点只向右移动,严格变短时才更新也能保留并列时更早的左端点。时间为 O(n+m)O(n+m),存图画与频次需要 O(n+m)O(n+m) 空间。

这里的条件必须落实为频次判断:kind=mkind=m 表示已经覆盖全部画家,cnt[a[l]]>1cnt[a[l]]>1 表示删除最左作品仍保留该画家的其他作品。每次删除都不改变已出现的画家集合。若某个起点曾被删除,以后即使右端继续右移,也总能用保留下来的更晚起点得到同样完整且更短的区间,所以左端不需要回退。

这种维护连续区间的同向双指针也称为滑动窗口。名称本身并不能确定收缩条件:本题依据“同一画家还有其他作品”删除左端;换成其他约束,必须重新证明删除后仍满足什么条件、为什么不会漏掉答案。

4. 区间合并

本节与下一节使用自足练习“区间覆盖长度”,完整约定如下。原资料中的内网题面无法作为离线资料的前提。

简易题面:给定数轴上的 nn 个半开区间 [li,ri)[l_i,r_i),其中 li<ril_i<r_i。

请计算这些区间的并集长度。被多个区间覆盖的部分只能计算一次。输入第一行 nn,接下来 nn 行各给出 li,ril_i,r_i,输出一个整数表示长度。

长度按数轴上的距离计算。例如 [1,4)[1,4) 长度为 4−1=34-1=3,不是把整数 1,2,3,41,2,3,4 都数进去得到 44。半开区间包含左端,不包含右端;单个端点本身没有长度,但端点是否属于区间会影响后面的重叠数问题。

数据范围:1≤n≤2×1051\le n\le2\times10^5,−109≤li<ri≤109-10^9\le l_i<r_i\le10^9。

先按左端点升序排列,维护尚未结算的最后一个合并区间 [l,r)[l,r)。新区间左端不超过 rr 时,两段重叠或相接,可以合并;否则旧区间已经结束。由于后续区间左端只会更大,旧区间不会再与它们相接,可以把长度计入答案。

用按左端点排好序的 [1,4),[2,3),[4,6),[8,9)[1,4),[2,3),[4,6),[8,9) 手算:

新读入区间与待结算区间的关系新的待结算区间已结算长度
[1,4)[1,4)初始化[1,4)[1,4)00
[2,3)[2,3)完全包含在原段内[1,4)[1,4)00
[4,6)[4,6)在端点相接[1,6)[1,6)00
[8,9)[8,9)中间有空隙[8,9)[8,9)55
输入结束结算最后一段无66

第二行说明右端必须取最大值,不能直接改成新右端 33,否则已经覆盖的 [3,4)[3,4) 会丢失。遇到空隙时才把旧段永久计入答案,因为排序保证以后不会再读到能填回旧空隙的区间。

以下全局数组 aa 保存区间,容量为 200010200010,每项的 l,rl,r 字段使用 long long\texttt{long long},比较函数 cmp\texttt{cmp} 按左端点升序排列。题目保证至少有一个区间。

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
struct Node{
    long long l,r;
}a[N];
bool cmp(Node x,Node y){
    return x.l<y.l;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%lld%lld",&a[i].l,&a[i].r);
    sort(a+1,a+n+1,cmp);
    long long l=a[1].l,r=a[1].r,ans=0;
    for(int i=2;i<=n;++i){
        if(a[i].l<=r)r=max(r,a[i].r);
        else{
            ans+=r-l;
            l=a[i].l;
            r=a[i].r;
        }
    }
    ans+=r-l;
    printf("%lld\n",ans);
}

循环结束后仍有最后一段未结算,必须再累加一次。对半开区间求并集长度时,[1,4)[1,4) 与 [4,7)[4,7) 可以合为 [1,7)[1,7),长度仍是 66;这不表示两段存在重叠。排序需要 O(nlog⁡n)O(n\log n) 时间,扫描需要 O(n)O(n) 时间,扫描额外空间为 O(1)O(1)。

5. 扫描线

仍以区间覆盖长度为例。区间合并维护并集的端点;扫描线则按坐标顺序维护当前覆盖次数,也能进一步统计重叠情况。

5.1 为什么只在端点处理事件

若坐标只有几百,可以用第四章的差分记录每个位置的覆盖次数。但这里坐标可能为负,跨度可达 2×1092\times10^9,按每个整数坐标开数组已经不合适。真正能改变覆盖次数的位置只有区间端点;端点之间无论相隔一米还是十亿米,状态都不变。于是可以只保存这些变化位置,并保留它们之间的真实距离。

5.2 把端点变成事件

每个半开区间 [li,ri)[l_i,r_i) 产生两个事件:在 lil_i 处覆盖次数增加 11,在 rir_i 处减少 11。把全部事件按坐标排序。相邻事件坐标之间没有区间开始或结束,覆盖次数保持不变,因此只需处理端点,不必逐个枚举坐标。

设当前事件坐标为 xx,上一个事件坐标为 prepre,处理当前事件前的覆盖次数为 cntcnt。它对应的是 [pre,x)[pre,x):若 cnt>0cnt>0,答案增加 x−prex-pre;然后统一处理坐标 xx 上的所有增减,得到右侧下一段的覆盖次数。

例如区间 [1,4)[1,4)、[2,5)[2,5)、[5,7)[5,7):

当前坐标此前一段此前覆盖次数增加的长度处理同坐标事件后的覆盖次数
11无000011
22[1,2)[1,2)111122
44[2,4)[2,4)222211
55[4,5)[4,5)111111
77[5,7)[5,7)112200

总覆盖长度为 66。坐标 55 上同时发生一次结束和一次开始,统一处理后的覆盖次数仍为 11。

扫描线在相邻端点间保持覆盖次数,坐标 5 的加一减一合并处理

处理坐标 55 之前,cnt=1cnt=1 对应的是左边的 [4,5)[4,5);处理完坐标 55 的两个事件后,新的 cnt=1cnt=1 对应右边的 [5,7)[5,7)。两次数值恰好相同,但对应的区间不同。把状态对应哪一段说清楚,才能确定代码里的更新顺序。

5.3 先结算长度,再更新状态

以下 ee 是全局事件数组,容量至少为 400010400010,每项包含坐标 xx 和变化量 vv。已为每个区间存入 (li,1)(l_i,1)、(ri,−1)(r_i,-1),事件数 m=2nm=2n。坐标、距离和答案使用 long long\texttt{long long},覆盖次数使用 int\texttt{int}。比较函数 cmpcmp 按事件坐标升序排列。

#include <bits/stdc++.h>
using namespace std;
const int N=400010;
struct Node{
    long long x;
    int v;
}e[N];
bool cmp(Node a,Node b){
    return a.x<b.x;
}
int main(){
    int n,m=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        long long l,r;
        scanf("%lld%lld",&l,&r);
        e[++m]={l,1};
        e[++m]={r,-1};
    }
    sort(e+1,e+m+1,cmp);
    long long ans=0,pre=e[1].x;
    int cnt=0,i=1;
    while(i<=m){
        long long x=e[i].x;
        if(cnt>0)ans+=x-pre;
        while(i<=m&&e[i].x==x){
            cnt+=e[i].v;
            ++i;
        }
        pre=x;
    }
    printf("%lld\n",ans);
}

必须先按旧覆盖次数结算 [pre,x)[pre,x),再更新坐标 xx 处的事件。若先更新,会把右侧区间的状态错误地用于左侧长度。相同坐标统一处理,也能避免把事件处理到一半的临时计数当成真实重叠数。求最大重叠数时,应在同坐标事件全部处理完后记录覆盖次数。

对于本题的非空半开区间,求最大重叠次数时也应在同坐标事件全部处理完后取最大值。例如 [1,2)[1,2) 和 [2,3)[2,3) 从未同时覆盖一个点,最大重叠为 11。如果在坐标 22 先处理开始事件并立即取最大值,会得到临时值 22,这个值不对应任何真实位置。

若改成实数闭区间 [1,2][1,2] 和 [2,3][2,3],它们在端点 22 的确同时存在,最大重叠应为 22。此时不能直接使用半开区间的合并事件规则:可以先加入当前坐标开始的区间,记录该点覆盖数,再移除在该点结束的区间。并集长度不受单点影响,但最大重叠数受影响,必须区分两个统计目标。

端点规则由区间含义决定。连续半开区间在 rr 处结束;整数闭区间 [l,r][l,r] 的差分才在 r+1r+1 处撤销。这里直接排序原坐标即可处理大坐标,不要求先离散化;即使使用离散化,长度仍须用原坐标之差计算。

共 2n2n 个事件,排序需要 O(nlog⁡n)O(n\log n) 时间,每个事件只处理一次,扫描需要 O(n)O(n) 时间,事件数组占用 O(n)O(n) 空间。

6. 作业

巩固练习

提高训练

留言

可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。