洛谷 P2947：[USACO09MAR] Look Up S ← 数组模拟+单调栈
【题目来源】
https://www.luogu.com.cn/problem/P2947
【题目描述】
约翰的 N(1≤N≤10^5) 头奶牛站成一排，奶牛 i 的身高是 Hi (1≤Hi≤10^6)。现在，每只奶牛都在向右看齐。对于奶牛 i，如果奶牛 j 满足 i<j 且 Hi<Hj，我们可以说奶牛 i 可以仰望奶牛 j。求出每只奶牛离她最近的仰望对象。
【输入格式】
第 1 行输入 N，之后每行输入一个身高 Hi。
【输出格式】
共 N 行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出 0。
【输入样例】
6
3
2
6
1
1
2
【输出样例】
3
3
0
6
6
0
【说明/提示】
6 头奶牛的身高分别为 3,2,6,1,1,2。
奶牛 #1,#2 仰望奶牛 #3，奶牛 #4,#5 仰望奶牛 #6，奶牛 #3 和 #6 没有仰望对象。
【数据规模】
对于 20% 的数据：1≤N≤10；
对于 50% 的数据：1≤N≤10^3；
对于 100% 的数据：1≤N≤10^5,1≤Hi≤10^6。
【算法分析】
单调栈不是一种新的栈结构，它只是栈的一种使用方式。也就是说，单调栈实际上就是普通的栈，只是在使用时始终保持栈内的元素是单调的。单调栈通过维护栈内元素单调性来高效解决特定范围查询问题，尤其擅长处理“下一个更大/更小元素”类问题。
【算法代码一：数组模拟（正序）】
#include <bits/stdc++.h>
using namespace std;const int maxn=1e6+5;
int h[maxn], c[maxn];
int stk[maxn];
int n,top;int main() {cin>>n;for(int i=1; i<=n; i++) cin>>h[i];for(int i=1; i<=n; i++) {while(top && h[stk[top]]<h[i]) {c[stk[top]]=i;top--;}stk[++top]=i;}while(top) {c[stk[top]]=0;top--;}for(int i=1; i<=n; i++) cout<<c[i]<<endl;return 0;
}/*
in:
6
3
2
6
1
1
2out:
3
3
0
6
6
0
*/【算法代码二：数组模拟（逆序）】
#include <bits/stdc++.h>
using namespace std;const int maxn=1e6+5;
int h[maxn],c[maxn];
int stk[maxn];
int n,top;int main() {cin>>n;for(int i=1; i<=n; i++) cin>>h[i];for(int i=n; i>=1; i--) {while(top && h[stk[top]]<=h[i]) top--;if(top) c[i]=stk[top];stk[++top]=i;}for(int i=1; i<=n; i++) cout<<c[i]<<endl;return 0;
}/*
in:
6
3
2
6
1
1
2out:
3
3
0
6
6
0
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/149454046
https://blog.csdn.net/hnjzsyjyj/article/details/117136341
https://blog.csdn.net/hnjzsyjyj/article/details/117370314
https://www.acwing.com/file_system/file/content/whole/index/content/5683794/