关于算法-数据结构:PAT甲级1101-Quick-Sort

题目粗心：

本题输出一个序列，蕴含 N 个正整数，如果一个数右边的所有数都比它小、左边的所有数都比它大，那么称这个数为序列的一个 pivot。求序列中 pivot 的个数。

算法思路：

因为判断任意地位的数字是否是 pivot 必须得晓得它是否比右边的都大，比左边的都小，那么就应用数组 leftMax，rightMin 别离保留以后地位的右边最小的数和左边最大的数，先从左往右遍历，如果以后地位j==0，那么就设置其右边最小的数字为 -1，如果不是第一个数字就在 j - 1 和 j - 1 右边的所有最小的数字中抉择一个更小的数字作为以后地位的右边的最小数字，而后从右往左遍历，如果以后的地位k==N-1, 那么就设置其左边的最大的数字为0x3ffffff, 如果不是最初一个数字，就在 k + 1 和 k + 1 左边的所有数字中抉择一个更大的数字作为以后数字左边所有数字中的最大数。最初再遍历一次数组元素，将符合条件的元素增加进 set 汇合中，而后输入即可。

留神点：

1、必须得输入两行，也就就是在没有 pivot 的时候须要输入 0 而后第二行得输入空行，测试点 2 考查。

提交后果：

AC 代码：

#include <set>
#include <cstdio>

using namespace std;

int main(){
    int N;
    scanf("%d",&N);
    int a[N];
    for (int i = 0; i < N; ++i) {scanf("%d",&a[i]);
    }
    int leftMax[N];// 保留以后地位的右边最大的数字
    int rightMin[N];// 保留以后地位的左边最小的数字
    for (int j = 0; j < N; ++j) {if(j==0){leftMax[j] = -1;// 最右边的数字右边没有数字
        } else  {leftMax[j] = a[j-1]>leftMax[j-1]?a[j-1]:leftMax[j-1];
        }
    }
    for (int k = N-1; k >=0 ; --k) {if(k==N-1){rightMin[k] = 0x3fffffff;
        } else {rightMin[k] = a[k+1]<rightMin[k+1]?a[k+1]:rightMin[k+1];
        }
    }
    set<int> pivots;//pivot 汇合
    for (int l = 0; l < N; ++l) {if(a[l]>leftMax[l]&&a[l]<rightMin[l]){pivots.insert(a[l]);
        }
    }
    printf("%d\n",pivots.size());
    set<int>::iterator it;
    for(it=pivots.begin();it!=pivots.end();++it){if(it!=pivots.begin()) printf(" ");
        printf("%d",*it);
    }
    printf("\n");
    return 0;
}