本文共 2111 字，大约阅读时间需要 7 分钟。

题目描述

定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标，即 $f(i)={\min }_{i<j\le n,a_j>a_i}\{$

输入格式

输出格式

输入输出样例

51 4 2 3 5

输出 #1

2 5 4 5 0

说明/提示

题目：本题求每个数后第一个大于它的数的下标。

思路：这是一道单调栈的模板题。单调栈维护两条规则：后进先出；栈内元素从栈底到栈顶保持单调性，要么从小到大，要么从大到小。

本题中，我们将这些数据视作 $n$ 个人的身高，每个人向右平视时，看不到矮的人，看到的一定是右边身高高于他的第一个人：

根据这一推断，我们看到的人肯定是一个比一个高的，而没看到的(人的数据)，留着也没用，直接丢弃。这样就符合单调性。那么什么时候丢弃这些没用的数据？当然是遇到比他高的人的时候。

于是我们可以从前往后遍历，维护一个单调递减栈：对于每个点，如果它的值大于栈顶下标表示的数组值，就依次弹出栈顶元素、并且置这些栈顶下标对应的答案为当前点的下标。如果值小于栈顶下标对应的数组值，就压栈。最后输出答案数组即可。

从前往后的代码如下：

#include 
   
    using namespace std;const int maxn = 3e6 + 10;int arr[maxn], ans[maxn], st[maxn], top = 0; //top==0表示空栈 int main() {
   	int n;	scanf("%d", &n);	for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);	//从栈底到栈顶的下标对应的数组值(优先级)依次递减 	for (int i = 1; i <= n; ++i) {
   		//将先进栈(前面的元素下标)且
   

或者从后往前遍历，维持一个单调递减栈：对于每个点 arr[i] ，弹出对应的数组值小于等于它的栈顶下标，直到栈顶下标对应的元素值 > arr[i] ，栈顶下标就是答案。然后将这个元素的下标压栈：

#include 
   
    using namespace std;const int maxn = 3e6 + 10;int arr[maxn], ans[maxn], st[maxn], top = -1; int main() {
   	int n;	scanf("%d", &n);	for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);	//从栈底到栈顶的下标对应的数组值(优先级)依次递减,	//后进先出,对应->第i个元素之后第一个大于a_i的元素的下标 	for (int i = n; i > 0; --i) {
   		//将先进栈(后面的)且不大于arr[i]的值的坐标清除掉,		//这一过程就是从i+1往后寻找第一个大于a_i的元素下标		while (top != -1 && arr[st[top]] <= arr[i]) --top;  		ans[i] = (top == -1 ? 0 : st[top]);	//top=-1表示之后没有大于arr[i]的值 		st[++top] = i; //存储arr的数组下标 	}	for (int i = 1; i <= n; ++i) {
   		if (i == 1) printf("%d", ans[i]);		else printf(" %d", ans[i]);	}    return 0;}
   

提交AC：

转载地址：https://memcpy0.blog.csdn.net/article/details/108268783 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！