Acwing 1591/ PAT 1101
算法
(扫描数组) $O(n)$
扫描三次数组,前两次来判断数组中的每个数是否满足作为分界数的条件。
第一次,从左到右扫描数组,时刻记录在数组左侧遇到过的最大值pl,如果遇到的第i项比pl还大,那么它满足作为划分的条件1。
第二次同理,从右到左扫描数组,时刻记录在数组右侧遇到过的最小值pr,如果遇到的第i项比pr还小,那么它满足作为划分的条件2。
第三次,以任意顺序遍历整个数组,把同时符合条件1和2的数作为答案输出。
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
int const N = 100010;
int h[N];
int l_c[N]; //比左端最大数还小的数
int r_c[N]; //比右端最小数还大的数
vector <int> res;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i ++ )
scanf("%d",&h[i]);
int pl = -1;
for (int i = 0; i < n; i ++ ){
if (h[i] > pl) {
pl = h[i];
l_c[i] = 1;
}
}
int pr = 1000001000;
for (int i = n - 1; i >= 0; i -- ){
if (h[i] < pr) {
pr = h[i];
r_c[i] = 1;
}
}
for (int i = 0; i < n; i ++ ){
if (l_c[i] && r_c[i])
res.push_back(h[i]);
}
printf("%d\n",res.size());
bool is_first = true;
for (int i = 0; i < res.size(); i ++ ){
if (is_first) is_first = false;
else printf(" ");
printf("%d", res[i]);
}
printf("\n");
return 0;
}