题目描述

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

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

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

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

输入格式

第一行包含整数N。

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

输出格式

共N 行，每行输出一个整数，其中第 i 行的输出整数表示编号为 i 的奶牛的最近仰视对象的编号;

如果不存在仰视对象，则输出0。

样列

输入样例：
6

3 2 6 1 1 2

输出样例：
3 3 0 6 6 0

算法 1 单调栈 O(n)

相当于找每个数右边离得最近且比它大的那个数下标.

一共会有四种组合

• 左小
• 左大
• 右小
• 右大

思路

遍历每一头奶牛,看其能成为谁的仰视对象, 用一个栈保存当前奶牛之前的奶牛

• 如果当前奶牛大于栈顶的奶牛,那一定可以成为其仰视的对象
• 从栈底 -> 栈顶依次递减

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
typedef pair<int, int> PII;
stack<PII> stk;

int a[N], s[N], n;


int main()
{
    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(stk.size() && stk.top().first < a[i])  // 当前待入栈元素比栈顶大，那么它就是栈顶元素的仰望对象
        {
            s[stk.top().second] = i; // 记录当前仰视的对象
            stk.pop();
        }
        stk.push({a[i], i});
    }

    for(int i = 1; i <= n; i ++ ) cout << s[i] << endl;

    return 0;
}

拓展

右边离得最近，且比他小

  for(int i = 1; i <= n ; i ++)
  {
    while(stk.size() && stk.top().first > a[i]) 
    {
         s[stk.top().second] = i;              
         stk.pop();
     }
    stk.push({a[i], i});
  }
 // 输出 ： 2 4 4 0 0 0 

左边离得最近，且比他大

 // 和【右大】代码相同，只不过从后给前面遍历
 for(int i = n; i > 0; i --)
 {
     while(stk.size() && stk.top().first < a[i]) 
     {
         s[stk.top().second] = i;                
         stk.pop();
     }
     stk.push({a[i], i});
 }
 // 输出 ：  0 1 0 3 3 3

左边离得最近，且比他小

 for(int i = n; i > 0; i --)
 {
    while(stk.size() && stk.top().first > a[i])  
    {
        s[stk.top().second] = i;                
        stk.pop();
    }
    stk.push({a[i], i});
 }
 // 输出 ：  0 0 2 0 0 5