题目大意

P5788

给出项数为n的整数数列a_{1 \dots n}。定义函数f(i)代表数列中第i个元素之后第一个大于a_i的元素的下标,即f(i)=\min\limits_{i<j\leq n, a_j > a_i} {j}。若不存在,则f(i)=0

试求出f(1\dots n)

解题思路

单调栈裸题。

单调栈,顾名思义,就是栈内元素满足单调性的栈。方法与单调队列很相似,只不过元素只通过一端进出。

在本题的方法中,我们要求出的是一个元素后第一个比它大的元素的下标。方法就是将元素依次入栈,然后进行操作。

假设序列为1 2 5 3 2 4 6,那么操作就是这样的:

a[1]=1先入栈
a[2]=2入栈,发现1<2,所以我们就找出了f(1)=2,将1出栈,因为它已经没用了
a[3]=5入栈,同理,f(2)=3,将2出栈
a[4]=3入栈,因为3<5,一时判断不出来5后面第一个比它大的是谁,所以先留着
a[5]=2入栈,同理,一起保留,栈内元素为5,3,2
a[6]=4入栈,此时发现2<4,说明找到了2后面的大于它的元素,将2出栈并且f[5]=6
然后继续发现栈内为5,3;3<4,所以说明找到了f(4)=6
接下来由于4<5,所以先留着,栈内为5,4
a[7]=6入栈,此时发现6>4,因此找到f(6)=7,同理,f(3)=7。
由于后面没有元素了,所以f(7)=0,完结

单调栈的操作就是这样进行的,每一次弹栈操作都能找到一个对应的f(i)。只是为了方便和速度快,栈内存储的不是对应的数字而是元素在原数组内的下标,方便判断f(i)

代码细节:

  • 使用手写栈而不是STL可以快将近1.5倍
  • 注意题目要求的是寻找第一个大于的元素下标,所以判断时要保留相等的元素不能弹栈,就是因为这个一开始我60分(不仔细读题的后果)

代码

  • 手写栈:
#include <cstdio>

const int maxn=3e6+5;
int s[maxn],top;
int a[maxn],f[maxn],n;

int main()
{
    top=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    for(int i=1;i<=n;i++)
    {
        while(top&&a[s[top]]<a[i])
            f[s[top--]]=i;
        s[++top]=i;
    }
    for(int i=1;i<=n;i++)
        printf("%d ",f[i]);
    return 0;
}
  • STL:
#include <cstdio>
#include <stack>
#include <cstring>
using std::stack;

const int maxn=3e6+5;
stack<int> s;
int a[maxn],f[maxn],n;

int main()
{
    memset(f,0,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    for(int i=1;i<=n;i++)
    {
        if(s.empty())
            s.push(i);
        else
        {
            while((!s.empty())&&a[s.top()]<a[i])
            {
                f[s.top()]=i;
                s.pop();
            }
            s.push(i);
        }
    }
    while(!s.empty())
    {
        f[s.top()]=0;
        s.pop();
    }
    for(int i=1;i<=n;i++)
        printf("%d ",f[i]);
    return 0;
}
最后修改日期:2020年2月25日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。