题目描述

约翰有N头奶牛，编号为1到N。

现在这N头奶牛按编号从小到大的顺序站成了一排，其中奶牛 i 的身高为Hi。

现在，每头奶牛都向它的右侧望向那些编号较大的奶牛，对于奶牛 i 如果存在一头奶牛 j 满足 i<ji<j 并且 Hi<HjHi<Hj，那么我们称奶牛 i 需要仰视奶牛 j。

请你求出每头奶牛的最近仰视对象。

输入格式
第一行包含整数N。

接下来N行，每行包含一个整数HiHi，其中第 i 行的数为编号为 i 的奶牛的高度。

输出格式
共 N 行，每行输出一个整数，其中第 i 行的输出整数表示编号为 i 的奶牛的最近仰视对象的编号，如果不存在仰视对象，则输出0。

数据范围
1≤N≤1051≤N≤105
1≤Hi≤106

样例

输入样例：

6 
3 
2 
6 
1 
1 
2 

输出样例：

3 
3 
0 
6 
6 
0

将当前奶牛,不断地和栈顶奶牛比较
如果说它身高大于栈顶奶牛,那么栈顶奶牛的仰视对象一定是当前奶牛,然后将栈顶奶牛出栈
进行下一次比较,直到栈为空或者栈顶奶牛身高高于它.最后再将我们当前奶牛的身高入栈.

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N=101000;//常数
int a[N],s[N];
stack<pair<int,int>> q;

int main(){
    int n;
    ios::sync_with_stdio(false);//优化不可少
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        while(q.size() && q.top().first < a[i]){//栈内有奶牛,且身高大于栈顶的奶牛
            s[q.top().second] = i;  //记录仰视的对象
            q.pop();
        }
        q.push(make_pair(a[i],i));//加入栈中
    }
    for(int i=1;i<=n;i++){
        cout<<s[i]<<endl;  //输出
    }
    return 0;
}