题目分析
Input：
第一行：一个正整数N（N<=100000）
第二行：N个互不相同的正整数，用空格分隔
Output：
第一行：符合条件的数的个数
第二行：按照升序输出
求解思路
- int类型的数组arr[N]：存放了原始数据
- maxBefore：当前左侧最大值（初始化为-1）
- minBehind：当前右侧最小值（初始化为1000000005）
- int类型的数组res[N]：存放结果
- bool类型的数组flag[N]：flag[i]指示arr[i]是否为我们要找的元素，若是，flag[i]=true；否则flag[i]=false。
- 在输入的时候，假设当前输入为arr[i]，判断arr[i]是否大于maxBefore，同时更新maxBefore和flag[i]的值。
- 逆序遍历数组，判断arr[i]是否小于minBehind，若不是，将flag[i]的值更新为false。若此时flag[i]为true，则arr[i]为我们要找的元素，存入res数组中。
- 输出时，若sum为0，则输出空的一行（必须输出空的一行，否则有的样例不能通过）；若sum不为0，调用sort()函数，将res数组升序排列后输出。
C++源码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int N;
int sum = 0;
cin>>N;
bool *flag = new bool[N];
int *arr = new int[N];
int *res = new int[N];
int maxBefore = -1;
int minBehind = 1000000005;
for(int i = 0; i < N; i++)
{
flag[i] = true;
}
for(int i = 0; i < N; i++)
{
cin>>arr[i];
if(arr[i] > maxBefore)
{
maxBefore = arr[i];
}
else
{
flag[i] = false;
}
}
for(int i = N - 1; i >= 0; i--)
{
if(arr[i] < minBehind)
{
minBehind = arr[i];
}
else
{
flag[i] = false;
}
if(flag[i])
{
sum = sum + 1;
res[sum - 1] = arr[i];
}
}
cout<<sum<<endl;
if(sum == 0)
{
cout<<endl;
}
else
{
//res[0..sum-1]
sort(res, res + sum);
for(int i = 0; i < sum; i++)
{
cout<<res[i];
if(i != sum - 1)
{
cout<<" ";
}
}
}
return 0;
}
