AcWing 600. 仰视奶牛（单调栈）

本是古典何须时尚 2022-10-27 06:15 11阅读 0赞

**上一篇博客：[AcWing 830. 单调栈][AcWing 830.]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[AcWing 600. 仰视奶牛][AcWing 600.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  数据范围
     *  输入样例
     *  输出样例
 *  题解
 *   *  解题思路
     *  解题代码

# 题目信息 #

## 题目描述 ##

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

现在这 **N** 头奶牛按编号从小到大的顺序站成了一排，其中奶牛 **i** 的身高为  H i H\_i Hi。每头奶牛都向它的右侧望向那些编号较大的奶牛，对于奶牛 **i** 如果存在一头奶牛 **j** 满足 **i < j** 并且  H i H\_i Hi <  H j H\_j Hj，那么我们称奶牛 **i** 需要仰视奶牛 **j**。

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

## 输入格式 ##

第一行包含整数 **N**。

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

## 输出格式 ##

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

## 数据范围 ##

**1 ≤ N ≤  1 0 5 10^5 105**  
 **1 ≤  H i H\_i Hi ≤  1 0 6 10^6 106**

## 输入样例 ##

> 6  
> 3  
> 2  
> 6  
> 1  
> 1  
> 2

## 输出样例 ##

> 3  
> 3  
> 0  
> 6  
> 6  
> 0

# 题解 #

## 解题思路 ##

本题同样也是一个单调栈的模板题，与上一个题目 [AcWing 830. 单调栈][AcWing 830.] 不同的是本题是`求每一个数右边第一个比其大的数的次序（从 1 开始）`。只要倒着遍历数组即可求出每一个数右边第一个比其大的数，将每一个数右边第一个比其大的数的坐标存起来，最后倒着输出即可。关于单调栈的详解请看上一篇博客 [AcWing 830. 单调栈][AcWing 830.]。

## 解题代码 ##

#include<iostream>
    #include<cstdio>
    using namespace std;
    
    const int N = 100010;
    int stk[N], h[N], n, top;
    int ans[N];
    
    int main() { 
        cin >> n;
        for (int i = 0; i < n; i++) scanf("%d", &h[i]);
        int k = 0;
        for (int i = n - 1; i >= 0; i--) { 
            while (top && h[stk[top]] <= h[i]) top--;
            if (top) ans[k++] = stk[top] + 1;
            else ans[k++] = 0;
            stk[++top] = i;
        }
        for (int i = k - 1; i >= 0; i--) printf("%d\n", ans[i]);
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![20210203203608568.png][]

[AcWing 830.]: https://ac-fun.blog.csdn.net/article/details/113406056
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 600.]: https://www.acwing.com/problem/content/description/602/
[20210203203608568.png]: /images/20221024/c6dbcd644fae41d5ba45f4e7c1fa9de7.png