数组中的最长山脉

845. 数组中的最长山脉

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：

B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

（注意：B 可以是 A 的任意子数组，包括整个数组 A。）

给出一个整数数组 A，返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

示例 1：

1
2
3

输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。

示例 2：

1
2
3

输入：[2,2,2]
输出：0
解释：不含 “山脉”。

提示：

0 <= A.length <= 10000
0 <= A[i] <= 10000

方法一：枚举山顶

我们对于数组 A 中的每个数使用一次中心扩展，即可求出以当前数为山顶的子数组长度。

class Solution {
    public int longestMountain(int[] A) {
        int ans = 0;
        for(int i = 0; i < A.length; i++){
            int l = i - 1, r = i + 1;
            while(l >= 0 && A[l] < A[l + 1]){
                --l;
            }
            while(r < A.length && A[r - 1] > A[r]){
                ++r;
            }
            if(l != i - 1 && r != i + 1){
                ans = Math.max(ans, r - l - 1);
            }
        }
        return ans;
    }
}

时间复杂度O(n^2)
空间复杂度O(1)

由于左侧山脚到山顶的序列是严格单调递增的，从山顶到右侧山脚的序列是严格单调递减的。我们可以计算从任意一个元素开始，向左右两侧最多可扩展的元素。

我们用 left[i]表示A[i]向左侧最多可以扩展的元素数目，用 right[i]表示A[i]向右侧最多可以扩展的元素数目。
$$
left[i]=\left{
\begin{aligned}
left[i - 1] + 1, \ \ A[i] > A[i - 1] \
0, \ \ A[i] \leq A[i - 1] 或 i =0\
\end{aligned}
\right.
$$

$$
right[i]=\left{
\begin{aligned}
right[i + 1] + 1, \ \ A[i] > A[i + 1] \
0, \ \ A[i] \leq A[i + 1] 或 i = n -1\
\end{aligned}
\right.
$$
计算出所有 left 和 right 后，枚举山顶，只有当left[i] 和 right[i]都大于 0 时，A[i]才能作为山顶。

class Solution {
    public int longestMountain(int[] A) {
        int n = A.length;
        if(n == 0){
            return 0;
        }
        int[] left = new int[n];
        int[] right = new int[n];

        for(int i = 1; i < n; i++){
            left[i] = A[i] > A[i - 1] ? left[i - 1] + 1 : 0;
        }
        for(int i = n - 2; i >= 0; i--){
            right[i] = A[i] > A[i + 1] ? right[i + 1] + 1 : 0;
        }

        int ans = 0;
        for(int i = 0; i < n; i++){
            if(left[i] != 0 && right[i] != 0){
                ans = Math.max(ans, left[i] + right[i] + 1);
            }
        }
        return ans;
    }
}

时间复杂度O(n)
空间复杂度O(n)

方法二：枚举山脚

当我们从左向右遍历整个数组 A 时，可以使用双指针的方法，一个枚举左侧山脚，另一个不断向右移动到右侧山脚。

山顶数组最少为 3 个元素，需要保证left + 2 < n和 A[left] < A[left + 1]。

我们将right 初始化为 left + 1，不断将其右移，直到不满足A[right] < A[right + 1]

如果 right = n - 1，此时已经无法形成山脉
如果 right 指向的是山顶，我们需要判断是否有 A[right] > A[right + 1]，如果right 指向的是山顶，不断右移 right 直到不满足 A[right] > A[right + 1]，此时 right 指向右侧山脚，A[left] 到 A[right]就对应着一座山脉。
右侧的山脚有可能是下一座山脉的左侧山脚，我们需要将 right 的值赋予 left，以便进行下一次枚举。在其他所有情况下，将right + 1赋给left。

class Solution {
    public int longestMountain(int[] A) {
        int n = A.length;
        int ans = 0;
        int left = 0;
        while(left + 2 < n){
            int right = left + 1;
            if(A[left] < A[left + 1]){
                while(right + 1 < n && A[right] < A[right + 1]){
                    ++right;
                }
                if(right < n - 1 && A[right] > A[right + 1]){
                    while(right + 1 < n && A[right] > A[right + 1]){
                        ++right;
                    }
                    ans = Math.max(ans, right - left + 1);
                }else{
                    ++right;
                }
            }
            left = right;
        }
        return ans;
    }
}

时间复杂度O(n)
空间复杂度O(1)