PTA乙级题 1045. 快速排序(25)

【题目链接】

自我感觉这题很难，因为容易超时，先上大佬写的代码。

#include<iostream> 
#include<stdio.h> 
#include<string.h> 
#include<string> 
#include<vector> 
#include<algorithm> 
using namespace std;  
int main(){  
    for(int n;scanf("%d",&n)!=EOF;){  
        vector<int>vec;  
        vector<int>res;  
        int *arr = new int[n];  
        memset(arr,0,n*sizeof(int));  
        int left_max = 0;  
        int right_min = 1000000000;  
        for(int i = 0;i < n;i++){  
            int temp;  
            scanf("%d",&temp);  
            vec.push_back(temp);  
        }  
        for(int i = 0;i < vec.size();i++){  
            if(vec[i] > left_max){  
                arr[i]++;  
                left_max = vec[i];  
            }  
        }  
        for(int i = vec.size()-1;i >= 0;i--){  
            if(vec[i] <= right_min){  
                arr[i]++;  
                right_min = vec[i];  
            }  
        }  
        for(int i = 0; i < n;i++){  
            if(arr[i] == 2){  
                res.push_back(vec[i]);  
            }  
        }  
        sort(res.begin(),res.end());  
        printf("%d\n",res.size());  
        if(res.size()){  
            printf("%d",res[0]);  
            for(int i = 1;i < res.size();i++){  
                printf(" %d",res[i]);  
            }  
            printf("\n");  
        }else{  
            printf("\n");  
        }  
        delete[] arr;  
    }  
    return 0;  
} 

下面是自己写的代码，有几个点运行超时。

#include<stdio.h>
int main()
{
    int n,i,j,flag=0,x=0;
    scanf("%d",&n);
    int a[n],b[n]={0};
    for (i=0;i<n;i++)
    scanf("%d",&a[i]);
    for (i=0;i<n;i++)
    {
        flag=0;
        for (j=0;j<i;j++)
        {
            if (a[j]>=a[i])
            {
                flag=1;
                break;
            }
        }
        for (j=i+1;j<n;j++)
        {
            if (a[j]<=a[i])
            {
                flag=1;
                break;
            }
        }
        if (flag==0)
        {
            b[x]=a[i];
            x++;
        }
    }
    if (x!=0)
    {
        printf("%d\n",x);
        for (i=0;i<x;i++)
        {
            printf("%d",b[i]);
            if (i!=x-1)
            printf(" ");
        }
    }
    else
    printf("%d",x);
    return 0;
}