题目描述

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

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

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

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

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

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

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

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

样例

输入样例：
6 
3 
2 
6 
1 
1 
2 
输出样例：
3 
3 
0 
6 
6 
0 

算法1

(单调栈) $O(n)$

由于每个元素最多只进一次栈，一共n个元素，所以时间复杂度为O(n)，单调栈问题主要解决了一个距离它最近的数值离他最近的数，这个数字可以在原数字的左边，可以再原数字的右边，可以比原数字大，也可以小，一共四种情况，本题相比单调栈的模板题的不同之处在于，本题是求右边的元素，所以我们要从后往前循环，采用结构体数组来存储高度和num(编号)，其余与单调栈模板一样

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct cow
{
    int num;
    int hi;
}a[N];
cow b[N];
int tt,n;
stack<int>temp;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       cin>>a[i].hi;
       a[i].num=i;
    }
    for(int i=n;i>=1;i--)
    {
        while(a[i].hi>=b[tt].hi&&tt)tt--;
        if(tt>0)temp.push(b[tt].num);
        else temp.push(0);
        b[++tt].num=a[i].num;
        b[tt].hi=a[i].hi;
    }
    while(temp.size())
    {
        cout<<temp.top()<<endl;
        temp.pop();
    }
    return 0;
}

算法2

(单调栈) $O(n)$

写完结构体数据突然发现可以使用pair这个数据结构.

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef pair<int,int>cow;
cow b[N],a[N];
int tt,n;
stack<int>temp;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       cin>>a[i].first;
       a[i].second=i;
    }
    for(int i=n;i>=1;i--)
    {
        while(a[i].first>=b[tt].first&&tt)tt--;
        if(tt>0)temp.push(b[tt].second);
        else temp.push(0);
        b[++tt].second=a[i].second;
        b[tt].first=a[i].first;
    }
    while(temp.size())
    {
        cout<<temp.top()<<endl;
        temp.pop();
    }
    return 0;
}