題目背景

模板題，無背景。

2019.12.12 更新數據，放寬時限，現在不再卡常了。

題目描述

給出項數為?n?的整數數列?a1…n?。

定義函數?f(i)?代表數列中第?i?個元素之后第一個大于?ai??的元素的下標，即?f(i)=mini<j≤n,aj?>ai??{j}。若不存在，則?f(i)=0。

試求出?f(1…n)。

輸入格式

第一行一個正整數?n。

第二行?n?個正整數?a1…n?。

輸出格式

一行?n?個整數表示?f(1),f(2),…,f(n)?的值。

輸入輸出樣例

輸入 #1復制

5
1 4 2 3 5

輸出 #1復制

2 5 4 5 0

說明/提示

【數據規模與約定】

對于?30%?的數據，n≤100；

對于?60%?的數據，n≤5×103?；

對于?100%?的數據，1≤n≤3×106，1≤ai?≤109。

解題思路

這道題是單調棧的模板題，在這道題之后我也寫過其他單調棧的題目，基本無差。

首先定義一個棧，將原數組逆序判斷，因為我們要比較i位置后面的數據。

當棧不為空且棧最頂端數據小于數組當前的數據時，將此時棧的數據踢出。

如果棧是空的，那么直接按題目要求輸入0，存入新數組中；如果不為空，那么就將此時棧中最頂端的下標存入所求新數組中。

每次循環都要將此次循環的下標存入棧中。

最后直接輸出所求的數組即可，完整代碼如下：

?
#include<bits/stdc++.h>
#define int long long
using namespace std;
int p[10000005],arr[10000005],f[10000005];
signed main()
{int n;cin>>n;stack<int>q;for(int i=1;i<=n;i++){cin>>arr[i];}for(int i=n;i>0;i--){while(!q.empty()&&arr[q.top()]<=arr[i]){q.pop();}if(q.empty()){f[i]=0;}else{f[i]=q.top();}q.push(i);}for(int i=1;i<=n;i++){cout<<f[i]<<" ";}return 0;
}?