第二题仅需遍历一遍存极小值坐标即可

疯狂过山车

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;
    }
全部评论

相关推荐

点赞 评论 收藏
分享
每晚夜里独自颤抖:这个在牛客不是老熟人了吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-27 20:15
还能挽救吗?找同学帮忙看了一下&nbsp;字节怎么能如此对我
牛客26396789...:你这是严重红线,被发现你自己永远进不去,你那个同学直接走人,你还敢宣扬
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务