返回信息流极小值点要记录一下，当前降序时要和前一极小值点比较，小于并且计数小于前一极值点删除次序，则更新当前计数=前一极值点删除次序，极值点前找
struct record {
int num;
int count;
int last;
void set(int num, int count) {
record::num = num;
record::count = count;
}
};
int fun(int array[], int n) {
if (n <= 1)
return 0;
record *min = new record[n / 2 + 1];
int cursor = 0;
min[cursor].set(array[0], 0);
min[cursor].last = -1;
int ans = 0;
for (int i = 1; i < n; i++) {
for (; i < n && array[i] > array[i - 1]; i++); // 局部升序处理
int tmp = 1;
int k = cursor;
while (i < n && array[i] <= array[i - 1]) { // 局部降序处理
if (array[i] <= min[k].num) {
if (tmp < min[k].count) {
tmp = min[k].count;
}
k = min[k].last;
}
else {
tmp++;
i++;
}
}
if (ans < tmp) {
ans = tmp;
}
k = cursor;
cursor++;
min[cursor].set(array[i - 1], tmp);
for (; array[i - 1] <= min[k].num; k = min[k].last);
min[cursor].last = k;
}
return ans;
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #95434同步于 2018/4/4
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
Re: 微软拔树题的一种O(n)想法
zhouliyan111
2018/4/4镜像同步12 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
【 在 zhouliyan111 的大作中提到: 】
: 极小值点要记录一下，当前降序时要和前一极小值点比较，小于并且计数小于前一极值点删除次序，则更新当前计数=前一极值点删除次序，极值点前找
: struct record {
: int num;
: ...................
思路一样，这样是O(n)
【 在 w1252675615 的大作中提到: 】
:
: 思路一样，这样是O(n)
我刚才例子举错了，
是{1, 5, 4, 3, 5, 4, 5, 3}
去除顺序：
0, 1, 2, 3, 1, 2, 1, 4
最后的3与极小值点3有关，跳过了极小值点4
【 在 zhouliyan111 的大作中提到: 】
:
: 我刚才例子举错了，
: 是{1, 5, 4, 3, 5, 4, 5, 3}
: ...................
没人关注，不开心，删帖删帖
【 在 Saerdna 的大作中提到: 】
: [2,1] 的处理结果是?
int[] a = {3,6,9,8};
int[] b = {3,2,1,2,3,2,1,5,4,3,2,1,5,4};
int[] c ={2,1};
三个例子全过了[ema3]
【 在 w1252675615 的大作中提到: 】
: public class Pulltree {
: public static int getTimes(int[] trees) {
: if (trees == null || trees.length < 2) return 0;
: ...................
我举得例子，你的是错的，输出3,应该是4
感觉最后出现连续等于是比较特殊的情况，我再想想，话说你两层for循环……并不理解你的思路
【 在 zhouliyan111 (舟) 的大作中提到: 】
: 我举得例子，你的是错的，输出3,应该是4