小Hi最近在关注股票,为了计算股票可能的盈利,他获取了一只股票最近N天的价格A1~AN。
小Hi想知道,对于第i天的股票价格Ai,几天之后股价会第一次超过Ai。
假设A=[69, 73, 68, 81, 82],则对于A1=69,1天之后的股票价格就超过了A1;对于A2=73,则是2天之后股票价格才超过A2。
输入
第一行包含一个整数N。
以下N行每行包含一个整数Ai。
对于50%的数据,1 ≤ N ≤ 1000
对于100%的数据,1 ≤ N ≤ 100000, 1 ≤ Ai ≤ 1000000
输出
输出N行,其中第i行代表对于第i天的股票价格Ai,几天之后股价会第一次超过Ai。
如果Ai+1~AN之内没有超过Ai,输出-1
--------------------------------------------------------------------------------------------------------------------------------------------------------
维护一个单调递减的队列,每push一个元素,pop掉所有小于他的元素,而pop掉的这些元素的结果正是当前元素。
每个元素进出队列各一次,复杂度为2N
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100100; int q_val[N],q_ind[N]; int ans[N]; int q_rear = 0; int main(){ int n,tint; cin>>n; for(int i=0;i<n;i++,q_rear++){ scanf("%d",&tint); while(q_rear>0&&q_val[q_rear-1]<tint){ q_rear--; ans[q_ind[q_rear]]=i-q_ind[q_rear]; } q_val[q_rear]=tint; q_ind[q_rear]=i; } while(q_rear-->0) ans[q_ind[q_rear]]=-1; for(int i=0;i<n;i++) printf("%d ",ans[i]); return 0; }