题解 单调栈结构

这是一道较为入门的模拟题，新手们都可以拿这道题练手

看了题目后我们不难发现，它把时限开到了2s,并且1≤n≤1000000，如果暴力去模拟，肯定会超时

大家的思路一般是不是

• 先读入

• 用一个循环枚举i，然后再套一个循环求比arr[ i ]小的靠左位置

• 用同样的方法来求靠右的位置

这样提交了在n=1000000时很难过，跑得很慢，容易TLE超时（我没有试过，可能刚好卡过）

于是我想到了如下的方法，代码里面有注释

代码自带防抄袭功能，请勿照搬，后果自负

注：虽然代码防作弊，但保证核心理解的地方正确，不会误导人

here is my code：

 # include <iostream>
# include <cstdio>
# include <cmath>
# include <cstring>
# include <algorithm>
using namespace std;
int read();//自己写的快读函数，优化读入
int arr[1000005];//这个还要解释请再看一遍题
int ans[3];//储存答案的数组
int main()
{
    int n=read();
    for(int i=0;i<n;i++)//读入
    {
        arr[i]=read();
    }
    for(int i=0;i<n;i++)
    {
        int flag1=0,flag2=0;//flag1是否找到左边答案的标记，找到了为1，没找到为0
                              //flag2是标记右边的
        int j=1;//这是向两边跑的步数，！！！两边同时跑！！！
        while(1)//别看这个while（1）就想说超时
        {
            if(flag1&&flag2)break;//如果都找到了就跳出循环
            int l=i-j,r=i+j;//l是跑到左边的位置，r是右边
            if(l<0&&flag1==0)//边界判断
            {
                ans[1]=-1;
                flag1=1;//别忘了标记
            }
            if(r>=n&&flag2==0)//边界判断
            {
                ans[2]=-1;
                flag2=1;
            }

            if(arr[i]>arr[l]&&flag1==0)//找到左边一个比arr[ i ]小的
            {
                ans[1]=l;
                flag1=1;
            }
            if(arr[i]>arr[r]&&flag2==0)
            {
                ans[2]=r;
                flag2=1;
            }
            j++;//跑下一步
        }
        printf("%d %d\n",ans[1],ans[2]);//输出，其实ans就是为了方便存答案，换成变量也可以
    }
    return 0;
}
int read()//快读函数，读入得比scanf还快
{
    int ans=0,flag=-1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')
        {
            ch=getchar();
            flag=1;
            break;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        ans=(ans<<3)+(ans<<1)+ch-'0';
        ch=getchar();
    }
    return ans*flag;
}

看到这，你应该明白了，下面总结一下（qwq卖个萌）

做题的时候

• 首先认真审题是必须的

• 其次要认真思考一下哪种方法最优，对于这个方法是否还需要优化

• 做完后再想想哪个空间可以省，哪个时间还可以优化

• 培养做题认真思考的感觉，人非圣贤孰能无过，但跳进同一个坑两次那就是你态度有问题了

最后再不要脸地要个赞

end