B1045 快速排序/A1101 Quick Sort

思路

与上一题几个PAT思路类似，这题的难点在于两个数组的设置，一开始没想到
两个数组一个leftMax记录左边最大的值，rightMin记录右边最小的值

代码

#include<vector>
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int INT_MAX = 10000000000;
int main(){
    int n, count = 0;
    scanf("%d",&n);
    vector<int> input(n), leftMax(n), rightMin(n), ans;
    for(int i = 0; i < n; i++) scanf("%d",&input[i]);
    leftMax[0] = 0, rightMin[n-1] = INT_MAX;
    for(int i = 1; i < n; i++){
        leftMax[i] = max(leftMax[i-1],input[i-1]);
        //if(input[i-1]>leftMax[i-1])leftMax[i] = input[i-1];
    }
    for(int i = n - 2; i >= 0; i--){
        rightMin[i] = min(rightMin[i+1],input[i+1]);
        //if(input[i+1]<rightMin[i+1]) rightMin[i] = input[i+1];
    }
    for(int i = 0; i < n; i++){
        //printf("input[%d] = %d, rightMin[%d] = %d, leftMax[%d] = %d\n",i,input[i],i,rightMin[i],i,leftMax[i]);
        if(input[i]<=rightMin[i]&&input[i]>=leftMax[i]){
            count++;
            ans.push_back(input[i]);
        }
    }
    sort(ans.begin(),ans.end());
    printf("%d\n",count);
    for(int i = 0; i < count; i++) {
        printf("%d",ans[i]);
        if(i<count-1)printf(" ");
    }
    printf("\n");
    return 0;
}