题解 单调栈结构

单调栈结构(进阶)

http://www.nowcoder.com/questionTerminal/2a2c00e7a88a498693568cef63a4b7bb

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

看了题目后我们不难发现,它把时限开到了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

全部评论
参考你的代码C语言通过25%,出现栈溢出。C语言编写(不了解c++)为防止数组栈溢出,可以将判定条件if(arr[i]>arr[l]&&flag1==0)分解为:if(flag1==0){if(arr[i]>arr[l])}。右侧同理
1 回复 分享
发布于 2020-05-22 09:57
为什么我的核心代码的思路和你一样却只有75%,难道差在输入?输入用的是cin
点赞 回复 分享
发布于 2019-09-02 11:25

相关推荐

10-11 17:45
门头沟学院 Java
走吗:别怕 我以前也是这么认为 虽然一面就挂 但是颇有收获!
点赞 评论 收藏
分享
11-24 19:04
已编辑
湖南工商大学 Java
点赞 评论 收藏
分享
评论
5
收藏
分享
牛客网
牛客企业服务