LeetCode-845

题目

结果

代码

class Solution {
    public int longestMountain(int[] A) {
        if (A.length == 0) {
            return 0;
        }
        // mountain数组的值为：若以mountain[i]作为山顶，长度将会如何
        int[] mountain = new int[A.length];
        for (int i = 0; i < mountain.length; i++) {
            mountain[i] = length(A, i);
        }
        Arrays.sort(mountain);
        return mountain[A.length - 1];
    }

    private int length(int[] A, int index) {
        // 边界值必然不是山顶
        if (index == 0 || index == A.length - 1) {
            return 0;
        }
        // 不是极大值的不然不是山顶
        if (A[index - 1] >= A[index] || A[index + 1] >= A[index]) {
            return 0;
        }
        int length = 1;
        for (int i = index - 1; i >= 0; i--) {
            if (A[i] < A[i + 1]) {
                length++;
            } else {
                break;
            }
        }
        for (int i = index + 1; i < A.length; i++) {
            if (A[i] < A[i - 1]) {
                length++;
            } else {
                break;
            }
        }
        return length;
    }
}

复杂度

时间复杂度：O（n²），实际一定比n²小，但又比n大一些

空间复杂度：O（n）