题目大意
给出项数为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;
}
留言