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

疯狂过山车

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

相关推荐

11-14 16:13
已编辑
重庆科技大学 测试工程师
Amazarashi66:不进帖子我都知道🐮❤️网什么含金量
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务