AT_donuts_2015_3 题解

ikunTLE · 2024-08-02 18:41:37 · 题解

题目传送门

题目大意

有 N 个人在排队，第 i 个人的身高是 H_i，请求出第 i 个人向前能看到多少个人（需满足依次越来越高）。

思路

考虑使用单调栈。用单调栈维护一个身高递减的序列，第 i 个答案就是当前栈的长度。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e5+10;
int a[N];
stack<int>st;
int main(){
    int n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        printf("%llu\n",st.size());
        while(!st.empty()&&st.top()<a[i])
            st.pop();
        st.push(a[i]);
    }
    return 0;
}