单调栈

时间限制: 1 Sec 内存限制: 128 MB
题目描述
有N个蚂蚁兄弟从左到右排成一行，每个蚂蚁见到比自己岁数大的蚂蚁就称为大哥。现在每只蚂蚁都先左看，寻找最近的大哥。找不到时输出0。
请编一个程序，帮助蚂蚁们计算每只蚂蚁的最近大哥是哪个？
输入
第一行2个正整数：N，N的范围是[1…100000]。
第二行：N个正整数，表示每只蚂蚁的年龄，每个数的范围是[0…1,000,000,000]。
输出
一行，N个整数，表示相应蚂蚁的最近大哥的编号。编号从1到N。
样例输入 Copy
6
8 6 3 3 5 1
样例输出 Copy
0 1 2 2 2 5

说实话我读错题了，想麻烦了。

• 思路就是 单调栈，找左侧离他最近的而且大于他的下标；

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <bits/stdc++.h>
#include <math.h>
typedef long long ll;
using namespace std;
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
const int MOD=10007;

inline int read() {
	int x=0;
	bool t=false;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}

priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

int main() {
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        while(cnt>=1&&a[dis[cnt]]<=a[i]){
            cnt--;
        }
        cout<<dis[cnt]<<" ";
        dis[++cnt]=i;
    }
    return 0;
}

上一个是从左到右，这一个题是从右向左

洛谷上的 单调栈模板题

思路就是从右往左分析；就是倒过来分析 <mark>注意数据范围</mark>

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <bits/stdc++.h>
#include <math.h>
typedef long long ll;
using namespace std;
const int maxn=3e6+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
const int MOD=10007;

inline int read() {
	int x=0;
	bool t=false;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}

priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

int main(){
    cin>>n;
    for( int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    
    for(int i=n;i>=1;i--)
    {
        while(a[dis[cnt]]<=a[i]&&cnt>=1){
            cnt--;
        }
        vis[i]=dis[cnt];
        dis[++cnt]=i;
    }
    for(int i=1;i<=n;i++)
        cout<<vis[i]<<" ";
    
    return 0;
}