本文共 1364 字，大约阅读时间需要 4 分钟。
在算法标签中搜了单调队列，搜到了这道题，但实际做起来发现并不是个单调队列，只是个双向队列的应用罢了…
朴素算法是暴力枚举，时间复杂度是O(n)，用双向队列优化后可以降为O(n)。 首先我们设置num[i]，表示第i位画家的作品出现的次数，显然当num[1~m]都不为0时就可以看遍所以画家的作品，我们用sum记录当前还有多少位画家的作品还未出现，则当sum=0时就可以更新[a,b]区间。 接下来就是双向队列发挥作用了。我们从头到尾遍历数组，如果当前元素k不等于队首元素，则将它入队，if(!num[k]) sum- -, num[k]++；如果当前元素k等于队首，先将它入队，num[k]++，然后将队首元素弹出队,更新num[]，再检查队首元素temp，num[temp]是否为1，不为1，继续弹出队并更新num[]，继续检查队首元素，直到判断到队首元素temp，num[temp]=1时才终止。代码如下：
#include#include #include #include #include #include using namespace std;typedef long long ll;const int maxn=1e6+5;const int inf=0x3f3f3f3f;int p[maxn],num[2005]={0};deque Q;inline void read(int &ret){ char c; while((c=getchar())&&(c>'9'||c<'0')); ret=0; while(c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar();}int main(){ int n,m; read(n); read(m); for(int i=1;i<=n;++i) read(p[i]); int a=0,b=inf,a0=1,b0=1,sum=m; for(int i=1;i<=n;++i) { if(Q.empty()) { Q.push_back(i); num[p[i]]++; sum--; } else { if(p[i]==p[Q.front()]) { Q.push_back(i); num[p[i]]++; while(!Q.empty()) //实际上此时队列Q是不会空的，所以这里的循环标志可以改为别的，只要为1就行 { num[p[Q.front()]]--; Q.pop_front(); a0++; //a0更新 if(num[p[Q.front()]]==1) break; } } else { Q.push_back(i); if(!num[p[i]]) sum--; num[p[i]]++; } } b0=i; //更新b0 if(!sum) //如果所以画家的作品都出现了，更新[a,b] { if(b0-a0
PS：这道题一开始看还是有点懵逼的，后来手推了一遍样例就找到思路了。所以动动手，不要懒，或许有不一样的收获。
转载地址：http://xwdci.baihongyu.com/