**一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],**\
**其左边的数都小于等于它,右边的数都大于等于它。**\
**能否只用一个额外数组和少量其它空间实现。**\
\
/\*\
// O(n\*n).\
\#include "stdafx.h"\
const int gc\_Size = 9;\
int arr[gc\_Size] = { 4, 8, 6, 5, 10, 12, 11, 15, 10 };\
\
void DoTask(){\
for( int i = 0; i \< gc\_Size; i++ )\
{\
int low = 0, high = gc\_Size - 1;\
while( low \< i && arr[low] \<= arr[i] ) low++;\
while( high \> i && arr[i] \<= arr[high] ) high--;\
if( high == low )\
cout \<\< arr[i] \<\< " ";\
}\
}\
\
int main(){\
DoTask();\
}\*/\
\
\#include "stdafx.h"\
// O(n).\
const int gc\_Size = 9;\
int arr[gc\_Size] = { 4, 8, 6, 5, 10, 12, 11, 15, 10 };\
\
void DoTask(){\
int arrAuxi[gc\_Size];\
arrAuxi[0] = numeric\_limits\<int\>::min();\
\
for( int i = 1; i \< gc\_Size; i++ )\
arrAuxi[i] = std::max(arrAuxi[i-1], arr[i-1]);\
\
if( arrAuxi[gc\_Size-1] \<= arr[gc\_Size-1] )\
cout \<\< arr[gc\_Size-1] \<\< " ";\
arrAuxi[gc\_Size-1] = numeric\_limits\<int\>::max();\
\
for( int i = gc\_Size - 2; i \>= 0; i-- )\
{\
int rightMin = std::min(arrAuxi[i+1], arr[i+1]);\
if( arrAuxi[i] \<= arr[i] && arr[i] \<= rightMin )\
cout \<\< arr[i] \<\< " ";\
arrAuxi[i] = rightMin;\
}\
}\
\
int main(){\
DoTask();\
}