第二题仅需遍历一遍存极小值坐标即可
疯狂过山车
https://ac.nowcoder.com/acm/contest/6219/B
public static int getMaxLength (int n, int[] num) {
int up = 0; // 记录极大值点个数
ArrayList<Integer> down = new ArrayList<>(); //记录极小值点坐标
if (n < 3) return 0; //少于三个节点无金字塔
if (num[0] < num[1]) down.add(0); //初始增则起点为极小值点
for (int i = 1; i < n - 1; i++) {
if (num[i] > num[i - 1] && num[i] > num[i + 1]) {
up++;
} else if (num[i] < num[i - 1] && (num[i] < num[i + 1] || num[i] == num[i + 1])) { //记录所有极小值点坐标
down.add(i);
}
}
if (num[n - 2] > num[n - 1]) down.add(n - 1); //末尾减则末尾为极小值点
if (up == 0) return 0; //无极大值无金字塔
if (down.size() == 2) return n; //极小值仅=2则极大值必定=1,全部金字塔
int ans = 0;
int len = down.size();
for (int i = 1; i < len; i++) { //每个金字塔长度为两个极小值中间距离
ans = Math.max(ans, down.get(i) - down.get(i - 1) + 1);
}
return ans;
}