/ Vijos / 题库 /

单调栈

单调栈

时间限制:1秒  内存限制:256M


【问题描述】

  给出项数为 \(n\) 的整数数列 \(a_1..a_n\)。定义函数 \(f(i)\) 代表数列中第 \(i\) 个元素之后第一个大于 \(a_i\) 的元素的下标,即 \(f(i)=min\{ j\ |\ i<j≤n\ 且\ a_j>a_i \}\)。若不存在,则 \(f(i)=0\)。

  试求出 \(f(1)..f(n)\) 的值。

【输入格式】

  第一行一个正整数 \(n\)。
  接下来的 \(n\) 行,每行一个整数,分别别表示正整数 \(a_1..a_n\)。

【输出格式】

  \(n\) 行,每行一个整数,分别表示 \(f(1)..f(n)\) 的值。

【输入输出样例】

 Input

5
1
4
2
3
5

 Output

2
5
4
5
0

【数据限制】

  对于 \(30\%\) 的数据,\(n≤100\)
  对于 \(50\%\) 的数据,\(n≤5×10^3\)
  对于 \(100\%\) 的数据,\(1≤n≤3×10^5\),\(1≤a_i≤10^9\)

【来源】

  Mr.he

信息

ID
1029
难度
3
分类
数据结构 | 队列单调队列 点击显示
标签
(无)
递交数
2
已通过
1
通过率
50%
被复制
5
上传者