洛谷 P2947：[USACO09MAR] Look Up S ← STL stack+单调栈

【题目来源】
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。

【算法分析】
单调栈不是一种新的栈结构，它只是栈的一种使用方式。也就是说，单调栈实际上就是普通的栈，只是在使用时始终保持栈内的元素是单调的。单调栈通过维护栈内元素单调性来高效解决特定范围查询问题，尤其擅长处理“下一个更大/更小元素”类问题。

【算法代码一：STL stack】

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;
int h[maxn], c[maxn];

int main() {
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>h[i];

    stack<int> st;
    for(int i=1; i<=n; i++) {
        while(!st.empty() && h[st.top()]<h[i]) {
            c[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }

    while(!st.empty()) {
        c[st.top()]=0;
        st.pop();
    }

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

    return 0;
}

/*
in:
6
3
2
6
1
1
2

out:
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=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
2

out:
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
2

out:
3
3
0
6
6
0
*/

【参考文献】
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/