单调栈10分求助
查看原帖
单调栈10分求助
186278
Saberlve楼主2020/11/5 09:04

每次弹出时对答案的贡献不就是i-s.top()-1吗,为什么不对呢

#include<bits/stdc++.h>
#define int long long
const int N=1000001;
using namespace std;
int a[N],ans=0,k;
stack<int> s;
signed main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(s.empty()||a[s.top()]>=a[i])
		s.push(i);
		else
		{
			while(!s.empty()&&a[s.top()]<a[i]) 
			{
				ans+=i-s.top()-1;
				s.pop();
			}
			s.push(i);
		}
	}
	if(!s.empty()) k=s.top();
	while(s.size()!=1) s.pop();
	ans+=k-s.top();
	cout<<ans;
}
2020/11/5 09:04
加载中...