题目解决方案
- 抓住一个核心的要点就是一个数想要出栈，1种情况是比它大的数都没有进来，另一种情况是比它大的都出去了。我们怎么判断是否有比它大的数呢？通过一个maxvalue来记录能弹出的最大值的最小值。你可能看到这个会有一些懵，我来解释一下。比如6 5 4这样的出栈顺序，我们读取6时，6是最大值，到5时，最大值是5了。如果再判断4-6会浪费时间，5已经可以弹出了，说明比五大的都没问题了，我们只需要判断4-5中间的数是否清理干净即可。
- 还有一个注意的点是栈的长度有限制，这个怎么解决呢就是通过判断出栈的数是否更新了最大值，如果更新最大值，前面的数弹出的都比它小。这样的话，我们可以判断里面最多有maxvalue-i(对应的下标)个数，看是否小于栈的容量即可。
- 具体的看代码细节吧。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int main(int argc, char** argv)
{
int m,n,k;
cin>>m>>n>>k;
for(int i=0;i<k;i++)
{
int flag[1001]={0};
int maxvalue=-1;
bool ans=true;
for(int j=0;j<n;j++)
{
int temp;
cin>>temp;
maxvalue=max(temp,maxvalue);
if(maxvalue==temp)
{
if(temp-j>m)
ans=false;
}
else
{
for(int k=temp+1;k<maxvalue;k++)
{
if(flag[k]==0)
ans=false;
}
}
flag[temp]=1;
maxvalue=temp;
}
if(ans)
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
|
