hiho 1620 - 股票价格3 - 无限制的单调队列?
2024-08-27 06:28:21
小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 = ;
int q_val[N],q_ind[N];
int ans[N];
int q_rear = ; int main(){
int n,tint; cin>>n;
for(int i=;i<n;i++,q_rear++){
scanf("%d",&tint);
while(q_rear>&&q_val[q_rear-]<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-->) ans[q_ind[q_rear]]=-;
for(int i=;i<n;i++) printf("%d\n",ans[i]);
return ;
}
最新文章
- spring-poi-excle往单元格写入图片
- div水平居中和垂直居中
- bash中变量+=,if大小判断,随机休眠
- RMQ和LCA
- C# 处理图像三种方法对比
- Selenium2(webdriver)入门之TestNG的使用
- mvc模式jsp+servel+dbutils oracle基本增删改查demo
- Linux添加硬盘和挂载
- 常见类——Object
- LeetCode90:Subsets II
- yii2修改默认控制器
- excel 删除重复项
- RobotFramework--环境安装1
- entity framework core 生成 postgresql 数据库实体
- LeetCode(34):搜索范围
- SSM项目实战
- AngularJS2.0教程(一)快速上手之基础知识
- ElasticSearch索引
- codevs 1862 最长公共子序列(求最长公共子序列长度并统计最长公共子序列的个数)
- windows常用运行命令总结