求!80tps单调栈!
查看原帖
求!80tps单调栈!
964890
zhexj楼主2024/7/9 17:10
#include <bits/stdc++.h>
using namespace std;
int n, a[300005], mx[300005], mn[300005], ans = 0;
stack<int> s1, s2;

void Get_max(int i)
{
	while(!s1.empty() && a[i] > a[s1.top()]) s1.pop();
	if(!s1.empty())
		mx[i] = s1.top();
	s1.push(i);
}

void Get_min(int i)
{
	while(!s2.empty() && a[i] < a[s2.top()]) s2.pop();
	if(!s2.empty())
		mn[i] = s2.top();
	s2.push(i);
	return ;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		Get_min(i);		
		Get_max(i);
	}
	int j = n;
	while(j >= 1)
	{
		int R = mx[j];
		while(mn[j] > R && mn[j] != 0) j = mn[j];
		ans++;
		j--;
	}
	printf("%d", ans);
	return 0;
}
2024/7/9 17:10
加载中...