1101 Quick Sort (25 分)

题目链接
用两个数组，一个记录左边的最大值，一个记录右边的最小值，如果是主元肯定是满足大于左边的最大，小于右边的最小。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn],minR[maxn],maxL[maxn],ans[maxn];
const int INF = 0x3fffffff;
int main(){
	int n,k=0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	maxL[0]=0;
	for(int i=1;i<n;i++){
		maxL[i] = max(a[i-1], maxL[i-1]);
	}
	minR[n-1]=INF;
	for(int i=n-2;i>=0;i--){
		minR[i] = min(a[i+1],minR[i+1]);
	}
	for(int i=0;i<n;i++){
		if(a[i]>maxL[i] && a[i] < minR[i]){
			ans[k++]=a[i];
		}
	}
	cout<<k<<endl;
	for(int i=0;i<k;i++){
		cout<<ans[i];
		if(i!=k-1) cout<<" ";
	}
	cout<<endl;
	return 0;
}