题目背景
模板题，无背景。
2019.12.12 更新数据，放宽时限，现在不再卡常了。
题目描述
给出项数为 n 的整数数列 a1…n。
定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai 的元素的下标，即 f(i)=mini<j≤n,aj>ai{j}。若不存在，则 f(i)=0。
试求出 f(1…n)。
输入格式
第一行一个正整数 n。
第二行 n 个正整数 a1…n。
输出格式
一行 n 个整数表示 f(1),f(2),…,f(n) 的值。
输入输出样例
输入 #1复制
5 1 4 2 3 5输出 #1复制
2 5 4 5 0说明/提示
【数据规模与约定】
对于 30% 的数据，n≤100；
对于 60% 的数据，n≤5×103 ；
对于 100% 的数据，1≤n≤3×106，1≤ai≤109。
#include<bits/stdc++.h> using namespace std; const int N=3e6+10; int n; int a[N]; int ret[N]; void test() { stack<int> st; for(int i=n;i>=1;i--) { while(st.size()&&a[st.top()]<=a[i]) st.pop(); if(st.size()) ret[i]=st.top(); st.push(i); } for(int i=1;i<=n;i++) { cout<<ret[i]<<" "; } } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } test(); return 0; }
