1.题目要求判断一个数组中，哪些元素可以作为当前数组组合的pivot（可以理解为经过了若干轮的快排后，pivot在最终的位置）。
2.这道题目需要考虑采用适当的数据结构，即小根堆和大根堆。
3.判断某个元素是否能够成为pivot，那么该元素左边数组应该构成一个大根堆，堆顶元素应该小于该元素，该元素的右边构成小根堆，堆顶元素大于该元素
4.左边的小根堆，一直插入即可，利用priority_queue，而右边则需要进行维护，需要编写仿函数。
5.右边的大根堆维护机制：建立哈希表times，记录每个元素出现的次数，每往后检测新元素数，把新元素出现的次数-1，同时检测大根堆的堆顶元素，如果出现次数为0则弹出，直至剩下出现次数不为0的堆顶。
There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a run of partition, could you tell how many elements could be the selected pivot for this partition?
For example, given N = 5 and the numbers 1, 3, 2, 4, and 5. We have:
- 1 could be the pivot since there is no element to its left and all the elements to its right are larger than it;
- 3 must not be the pivot since although all the elements to its left are smaller, the number 2 to its right is less than it as well;
- 2 must not be the pivot since although all the elements to its right are larger, the number 3 to its left is larger than it as well;
- and for the similar reason, 4 and 5 could also be the pivot.
Hence in total there are 3 pivot candidates.Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<= 105). Then the next line contains N distinct positive integers no larger than 109. The numbers in a line are separated by spaces.
Output Specification:
For each test case, output in the first line the number of pivot candidates. Then in the next line print these candidates in increasing order. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.
Sample Input:
5 1 3 2 4 5
Sample Output:
3 1 4 5
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
struct cmp
{
bool operator()(const int&a, const int&b)
{
return a > b;
}
};
int main(void)
{
int sum;
cin >> sum;
int *num = new int[sum];
map<int, int> times;
/*vector<int> times(100001, 0);*/
priority_queue<int> lq;
priority_queue<int,vector<int>,cmp> rq;
for (int i = 0; i < sum; i++)
{
scanf("%d", &num[i]);
times[num[i]]++;
rq.push(num[i]);
}
vector<int> ans(0);
for (int i = 0; i < sum; i++)
{
if (i>0) lq.push(num[i – 1]);
if (rq.size() != 0)
{//如果右边heap不为空
times[num[i]]–;//减少num[i]的次数，以维护右边的小根堆
while (rq.size() != 0 && times[rq.top()] == 0) rq.pop();//检测堆顶元素，出现次数是否为0，如果为0，证明应该被弹出，
if (rq.size() != 0 && num[i]>rq.top())
{
continue;
}
}
if (lq.size() != 0 && num[i] < lq.top())
{
continue;
}
ans.push_back(num[i]);
}
cout << ans.size() << endl;
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++)
{
printf("%d", ans[i]);
if (i != ans.size() – 1)
cout << " ";
}
cout << endl;//注意在后面添加换行
return 0;
}
[/c]