题目背景
模板题，无背景。
2019.12.12 更新数据，放宽时限，现在不再卡常了。
题目描述
给出项数为 nn 的整数数列 a_{1 \dots n}a1…n。
定义函数 f(i)f(i) 代表数列中第 ii 个元素之后第一个大于 a_iai 的元素的下标，即 f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}f(i)=mini<j≤n,aj>ai{j}。若不存在，则 f(i)=0f(i)=0。
试求出 f(1\dots n)f(1…n)。
输入格式
第一行一个正整数 nn。
第二行 nn 个正整数 a_{1\dots n}a1…n。
输出格式
一行 nn 个整数 f(1\dots n)f(1…n) 的值。
输入输出样例
输入 #1复制
5
1 4 2 3 5
输出 #1复制
2 5 4 5 0
概念：单调递增或单调减的栈，跟单调队列差不多，但是只用到它的一端
题意分析：给一个数字n代表输入n个数；第二行输入这n个数
结果输出每个数右边第一个比它大的数；若无输出0
1，双for历遍
对每一个历遍元素，运用一个for循环，去查找它右边第一个大于它的数
2，单调栈（重点讲）
以样本数据为例子：
5
1 4 2 3 5
 |
| |
| 满足条件2 |
| |
| 满足条件1 |
| |
| |
| |
| 满足条件1 |
| |
| |
| 满足条件2 |
| |
| 满足条件1 |
| |
| |
| 满足条件2 |
| |
| |
| 满足条件2 |
这就是单调栈运行的具体流程图 在本题中，我们在维护单调栈的同时，也需要记录其结果的对应下标 于是，我们需要 创建相关的数组来记录相应的数据
1,数据数组：记录输入的n个数 dataArrary[]
2.下标数组：记录历遍元素的下标 cursorArray[]
3.结果数组：记录最终的答案 answerArray[]
另需一个top值，来表示当前栈中的元素数量
条件1：若此时栈为空或历遍元素小于等于栈顶元素，把其加入栈中（压栈）
条件2：若此时历遍元素大于栈顶元素，弹出栈顶元素，循环，直至不满足条件2或栈为空
转换为对应的代码为：
for (int i = 1; i < data.length; i++) {
//满足条件二
while (top != 0 && data[i] > data[cursor[top]]) {
answer[cursor[top]] = i;
stack.pop();
top--;
}
//满足条件一
stack.push(data[i]);
top++;
cursor[top] = i;
}
数据转换过程：
| |
| dataArray=[0,1,4,2,3,5] cursorArray=[0,0,0,0,0,0] answerArray=[0,0,0,0,0,0] Top=0 i=1 data[1]=1 |
| 满足条件一 cursor[top]=i Top++; Top=1 cursorArray=[0,1,0,0,0,0] answerArray=[0,0,0,0,0,0] |
| |
| |
| |
| dataArray=[0,1,4,2,3,5] Top=1 i=2 data[i]=4 |
| While(满足条件二) Answer[cursor[top]]=i Top--; Top=0; cursorArray=[0,1,0,0,0,0] answerArray=[0,2,0,0,0,0] |
| |
| Top=0 满足条件一： cursor[top]=i Top++ Top=1 cursorArray=[0,2,0,0,0,0] answerArray=[0,2,0,0,0,0] |
| |
| |
| |
| dataArray=[0,1,4,2,3,5] cursorArray=[0,2,0,0,0,0] answerArray=[0,2,0,0,0,0] Top=1 i=3 data[i]=2 满足条件一： Top++ cursor[top]=i Top=2 cursorArray=[0,2,3,0,0,0] answerArray=[0,2,0,0,0,0] |
| |
| |
| dataArray=[0,1,4,2,3,5] cursorArray=[0,2,3,0,0,0] answerArray=[0,2,0,0,0,0] Top=2 i=4 dataArray[i]=3 While(满足条件2): Answer[curosr[top]]=i Top--; Top=1; cursorArray=[0,2,3,0,0,0] answerArray=[0,2,0,4,0,0] |
| |
| 满足条件1 Top++; Cursor[top]=i Top=2 cursorArray=[0,2,4,0,0,0] answerArray=[0,2,0,4,0,0] |
| |
| |
| dataArray=[0,1,4,2,3,5] cursorArray=[0,2,4,0,0,0] answerArray=[0,2,0,4,0,0] Top=2 i=5 dataArray[i]=5 While(满足条件2): answer[cursor[top]]=i Top-- Top=0; cursorArray=[0,2,4,0,0,0] answerArray=[0,2,5,4,5,0] |
| |
| |
放下源码：
import java.io.*;
import java.util.Stack;
public class 单调栈 {
public static void main(String[] args) throws IOException {
StreamTokenizer r = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter pr = new PrintWriter(new OutputStreamWriter(System.out));
Stack stack = new Stack();
r.nextToken();
int n = (int) r.nval;
int data[] = new int[n + 1];
int cursor[] = new int[n + 1];
int answer[] = new int[n + 1];
int top = 0;
//输入数据
for (int i = 1; i < data.length; i++) {
r.nextToken();
data[i] = (int) r.nval;
}
//维护单调栈
for (int i = 1; i < data.length; i++) {
//满足条件二
while (top != 0 && data[i] > data[cursor[top]]) {
answer[cursor[top]] = i;
stack.pop();
top--;
}
//满足条件一
stack.push(data[i]);
top++;
cursor[top] = i;
}
//输出结果
for (int i = 1; i < answer.length; i++) {
if (i != answer.length - 1) {
pr.print(answer[i] + " ");
pr.flush();
} else {
pr.print(answer[i]);
pr.flush();
}
}
}
}
顺便附赠一个C++代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6 + 10;
int data[maxn], cursor[maxn], answe[maxn], top = 0; //top==0表示空栈
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &data[i]);
//从栈底到栈顶的下标对应的数组值(优先级)依次递减
for (int i = 1; i <= n; ++i) {
//将先进栈(前面的元素下标)且<arr[i]的值的坐标清除掉
//并记录data[i]的下标作为前面的答案
while (top && data[cursor[top]] < order[i]) answer[cursor[top--]] = i;
curso[++top] = i; //存储arr的数组下标
}
for (int i = 1; i <= n; ++i) {
if (i == 1) printf("%d", answer[i]);
else printf(" %d", answer[i]);
}
return 0;
}