分享一下O(n)做法的思路
查看原帖
分享一下O(n)做法的思路
874411
ExtractStars楼主2024/10/12 22:46

这题要求求出max{a[l,r]}=min{b[l,r]}max\{ a[l,r]\}=min\{ b[l,r]\}的区间个数。 我们可以转化一下,转化成求max{a[l,r]}<=min{b[l,r]}max\{ a[l,r]\}<= min\{ b[l,r]\}的个数减去max{a[l,r]}<=min{b[l,r]}max\{ a[l,r]\}<= min\{ b[l,r]\}的个数,这样就可以直接用滑动窗口和单调队列求出,能把时间复杂度压缩到O(n)O(n)

2024/10/12 22:46
加载中...