蒟蒻求助,为什么#wa6
查看原帖
蒟蒻求助,为什么#wa6
1533449
Doctor_10086楼主2025/1/13 10:45
#include<iostream>
#include<deque>
#include<stack>
using namespace std;
const int max_n = 1e5 + 5;
struct num {
	long long no;
	long long value;
};
long long arr[max_n], num_ct, max_size = 0, flag = 0, res[max_n];//flag用于判断塞入数值的重复性,res存储arr中该数的下一个更大数的索引
deque <long long> que, que1;//que维持合法队列,que1维持单调队列用于判断合法队列que中当前最大值
stack<num> s;
void next_greater(long long res[])//单调递减栈,服务于下一个更大
{
	for (int i = num_ct - 1; i >= 0; i--) {
		while (!s.empty() && s.top().value <= arr[i])s.pop();
		num temp;
		temp.no = i;
		temp.value = arr[i];
		res[i] = s.empty() ? -1 : s.top().no;
		s.push(temp);
	}
}

int main()
{
#define int long long 
	cin >> num_ct;
	for (int i = 0; i < num_ct; i++)cin >> arr[i];
	next_greater(res);//res初始化完成
	for (int i = 0; i < num_ct; i++) {
			if (!que.empty() && (que.front() >= arr[i] || res[i - 1] == -1)) {//当出现<=最小数(que.front())或者出现一个数后方无比它更大的数时,清空队列,回溯队列原始状态
			que.clear();
			que1.clear();
			flag = 0;
		}
		while (!que1.empty() && que1.back() < arr[i])que1.pop_back();//单调递减队列,服务于范围内最大值
		while (!que1.empty() && que1.back() == arr[i]) {//特别的是,有重复元素即将入列时,flag发生变化
			que1.pop_back();
			flag = 1;
		}
		que.push_back(arr[i]);
		que1.push_back(arr[i]);
		if (arr[i] > que1.front())flag = 0;//再次出现比合法队列que最大值更大值时,flag再次回溯,因为此时重复值将不是最大值
		if (que.size() > max_size && flag == 0 && que.back() == que1.front())max_size = que.size();//只有当当前que大小大于之前记录的size最大值,且最值无重复,且最大值在最右端时才进行最大size的更新
	}
	max_size = max_size == 1 ? 0 : max_size;//当给出数据数值都一样时,通过上述的方式,最后会残余1个项,我们不能将它计入合法大小中,通过判断将其归零
	cout << max_size;
	return 0;
}
2025/1/13 10:45
加载中...