题目信息
题目描述
约翰有 N 头奶牛,编号为 1 到 N。
现在这 N 头奶牛按编号从小到大的顺序站成了一排,其中奶牛 i 的身高为 $H_i$。每头奶牛都向它的右侧望向那些编号较大的奶牛,对于奶牛 i 如果存在一头奶牛 j 满足 i < j 并且 $H_i$ < $H_j$,那么我们称奶牛 i 需要仰视奶牛 j。
请你求出每头奶牛的最近仰视对象。
输入格式
第一行包含整数 N。
接下来N行,每行包含一个整数Hi,其中第 i 行的数为编号为 i 的奶牛的高度。
输出格式
共 N 行,每行输出一个整数,其中第 i 行的输出整数表示编号为 i 的奶牛的最近仰视对象的编号,如果不存在仰视对象,则输出 0。
数据范围
1 ≤ N ≤ $10^5$
1 ≤ $H_i$ ≤ $10^6$
输入样例
6
3
2
6
1
1
2
输出样例
3
3
0
6
6
0
题解
解题思路
本题同样也是一个单调栈的模板题,与上一个题目 AcWing 830. 单调栈 不同的是本题是求每一个数右边第一个比其大的数的次序(从 1 开始)
。只要倒着遍历数组即可求出每一个数右边第一个比其大的数,将每一个数右边第一个比其大的数的坐标存起来,最后倒着输出即可。关于单调栈的详解请看上一篇博客 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;
}
未完待续,持续更新中……
个人博客:ACfun的blog 欢迎来访鸭!
本文题目讲解博客地址:AcWing 600. 仰视奶牛(单调栈)