题目描述

我们把数组 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。

样例

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

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

注意

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

跟进

• 你能仅用一遍扫描解决吗？
• 你能用 $O(1)$ 的空间解决吗？

算法

(线性扫描) $O(n)$

1. 定义两个指针 last 和 i，表示这一次遍历山脉的开始位置和当前的位置。
2. 定义两个布尔变量 up 和 down，分别表示是否出现过上升和下降。
3. 初始时，last 指向 0，i 指向 1，布尔遍历均为 false。
4. 如果 A[i] == A[i - 1]，则说明下一个山脉需要从 i 位置开始，故 last = i，布尔变量都变为 false。
5. 如果 A[i] > A[i - 1]，即上升状态，这时如果已经出现过了下降，则说明这是第二次上升，此时已经不合法了。故 last = i - 1，因为可以从上一个位置开始；up = true，down = false。如果没有出现过下降，则合法。
6. 如果 A[i] < A[i - 1]，即下降状态，这是如果没有出现过上升，则不合法，下一个山脉需要从 i 位置开始，故 last = i，布尔变量都变为 false。
7. 在每次循环末尾，如果 up 和 down 都出现过，则更新答案 i - last + 1。

时间复杂度

• 仅遍历一次数组，故时间复杂度为 $O(n)$。

空间复杂度

• 仅定义了常数个变量，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int longestMountain(vector<int>& A) {
        int n = A.size(), ans = 0;
        int last = 0;
        bool up = false, down = false;
        for (int i = 1; i < n; i++) {
            if (A[i] == A[i - 1]) {
                last = i;
                up = down = false;
            }
            else if (A[i] > A[i - 1]) { // up
                if (down) {
                    down = false;
                    last = i - 1;
                }
                up = true;
            }
            else {  // down
                if (!up) {
                    last = i;
                    down = false;
                }
                else {
                    down = true;
                }
            }
            if (up && down)
                ans = max(ans, i - last + 1);
        }
        return ans;
    }
};