1.题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805377432928256
基于快排背景，其实就是找主元。

2.思路

利用继承关系求出每个元素A[i]的左边的最大值和右边的最小值（注意：要使得A[i]的左边的左右元素都比A[i]要小，所以要找A[i]左边的最大值进行比较）。
（1）A[0]~A[i-2]的最大值即leftMax[i-1]，而A[0]~A[i-1]的最大值即leftMax[i]，for循环内的判断如下：

  

   

    

     

    
    

     

      if(A[i-1]>leftMax[i-1])
     
    
   

    

     

    
    

     

          leftMax[i]=A[i-1];
     
    
   

    

     

    
    

     

      else if(A[i-1]<leftMax[i-1])
     
    
   

    

     

    
    

     

          leftMax[i]=leftMax[i-1];//直接继承上个元素记录的max
     
    
  
 

（2）同理也可以用rightMin数组记录序列A的每一位的最小位（不含本位），即rightMin[i]表示A[i+1]~A[n-1]的最小值（初值rightMin=INF，从右到左遍历），和上面方法一样for遍历一次。
（3）最后一次for遍历A序列进行判断，如果leftMax[i]小于A[i]，且rightMin[i]大于A[i]，则可以判断A[i]是主元，并记录到ans[i]数组中最后输出即可。

3.代码

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      const int MAXN=100010;
     
    
   

    

     

    
    

     

      const int INF=0x3fffffff;  //一个很大的数
     
    
   

    

     

    
    

     

      //a为序列，leftMax和rightMin分别为每一位左边最大的数和右边最小的数
     
    
   

    

     

    
    

     

      int a[MAXN],  leftMax[MAXN]  ,rightMin[MAXN];
     
    
   

    

     

    
    

     

      //ans记录所有主元,num为主元个数
     
    
   

    

     

    
    

     

      int ans[MAXN],num=0;
     
    
   

    

     

    
    

     
   
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	int n;
     
    
   

    

     

    
    

     
	scanf("%d",&n);
     
    
   

    

     

    
    

     
	for(int i=0;i<n;i++){
     
    
   

    

     

    
    

     
		scanf("%d",&a[i]);  //输入序列元素
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	leftMax[0]=0;   //A[0]左边没有比它大的数
     
    
   

    

     

    
    

     
	for(int i=1;i<n;i++){
     
    
   

    

     

    
    

     

      		leftMax[i]=max(    leftMax[i-1]   ,   a[i-1]  ); //由i-1推得i
     
    
   

    

     

    
    

     
		//注意加头文件algorithm后才能直接用max或min
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	rightMin[n-1]=INF;  //A[n-1]右边没有比它小的数
     
    
   

    

     

    
    

     
	for(int i=n-2;i>=0;i--){
     
    
   

    

     

    
    

     

      		rightMin[i]=min( rightMin[i+1]   ,  a[i+1] );//由i-1推得i
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	for(int i=0;i<n;i++){
     
    
   

    

     

    
    

     
		//左边所有数比它小，右边所有数比它大
     
    
   

    

     

    
    

     
		if(	leftMax[i]<a[i]		&&  rightMin[i]>a[i]){
     
    
   

    

     

    
    

     

      			ans[num++]=a[i];  //记录主元
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("%d\n",num);  //输出主元个数
     
    
   

    

     

    
    

     
	for(int i=0; i<num; i++){
     
    
   

    

     

    
    

     
		printf("%d",ans[i]);  //依次输出所有主元
     
    
   

    

     

    
    

     
		if(i<num-1)  printf(" ");
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("\n");  //必须有换行
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

4.注意点

（1）暴力判断会超时。
（2）当主元为0个时，第二行虽然没输出主元，但也要输出一个换行。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/98374894