解题笔记（27）――找数组中的特定元素 - wuzhekai的专栏 - 博客频道 - CSDN.NET
问题描述：一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。
思路：如果能用两个辅助数组，那么相对来说简单一点，可定义数组Min和数组Max，其中Min[i]表示自a[i]之后的最小值（包括a[i]），Max[i]表示自a[i]之前元素的最大值。有了这两个辅助数组后，对于a[i]，如果它大于Max[i-1]并且小于Min[i+1]，那么就符合要求。
void FindElements_Solution2(int *pArray, int len)
{
if(pArray == NULL || len <= 0 )
return ;
int *pMin = new int[len];
int Max;
int i;
Max = pArray[0];
pMin[len-1] = pArray[len-1];
for(i = len - 2; i >= 0; i--) //计算自i开始最小值的辅助数组
pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i];
if(pArray[0] <= pMin[0]) //检查第1个元素是否满足条件
cout<<pArray[0]<<' ';
for(i = 1; i < len - 1; i++)
{
if(pArray[i] >= Max && pArray[i] <=pMin[i+1]) //满足这个关系式的元素符合要求
cout<<pArray[i]<<' ';
Max = (Max < pArray[i])? pArray[i]: Max; //更新当前最大值
}
if(pArray[len-1] >= Max) //检查第len个元素是否满足条件
cout<<pArray[i];
cout<<endl;
delete [] pMin;
pMin = NULL;
}
Read full article from 解题笔记（27）――找数组中的特定元素 - wuzhekai的专栏 - 博客频道 - CSDN.NET