Java-LeetCode845. 数组中的最长山脉-onwPass | twoPass

• 算法：twoPass
  • 1.空间换取时间
  • 2.up数组记录前面有多少个连续比自己小的数，down数组记录后面有多少个连续比自己小的数
  • 3.第二次遍历计算最长山脉长度

public int longestMountain(int[] A) {
    int N = A.length;
    int[] up = new int[N];
    int[] down = new int[N];
    for (int i = 1; i < A.length; i++) {
        if (A[i] > A[i-1]) {
            up[i] = up[i-1] + 1;
        }
        if (A[N-i-1] > A[N-i]) {
            down[N-i-1] = down[N-i] + 1;
        }
    }

    int length = 0;
    for (int i = 1; i < A.length - 1; i++) {
        if (up[i] > 0 && down[i] > 0) {
            length = Math.max(length, up[i] + down[i] + 1);
        }
    }
    return length;
}

• 算法-onePass
  • 1.遍历每一个元素作为山脉的起始位置，计算山脉的长度
  • 2.下一个山脉的起始位置是上一个山脉的结束位置，优化时间

public int longestMountain(int[] A) {
    int length = 0;
    for (int i = 0; i < A.length - 2; i++) {
        if (A[i+1] > A[i]) {
            int upper = i + 1;
            while (upper + 1 < A.length && A[upper + 1] > A[upper]) {
                upper++;
            }
            int lower = upper + 1;
            if (lower < A.length && A[lower] != A[upper]) {
                while (lower + 1 < A.length && A[lower + 1] < A[lower]) {
                    lower++;
                }
                length = Math.max(length, lower - i + 1);
                i = lower - 1;
            }
        }
    }
    return length;
}