https://leetcode-cn.com/problems/longest-mountain-in-array/

难度：中等

---

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

  输入：[2,1,4,7,3,2,5]

  输出：5

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

示例 2：

  输入：[2,2,2]

  输出：0

  解释：不含 “山脉”。

提示：

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

解法1：状态判断

  根据题意，我们需要寻找数组中的最长山脉，而这条山脉一定会是连续的，因此我们可以找到一种方案只遍历一次数组，计算每条山脉的长度，并从中选取最长的山脉。

  对于数组中的数字 A[i] （0 <= i < length - 1），它只有三种状态：

• 状态1：当前数字小于下一数字：A[i] < A[i+1]，这种情况，它可能会是一条山脉的左半组成部分
• 状态2：当前数字等于下一数字：A[i] == A[i+1]，这种情况，这个数字可能会是山脉的右半部分的结束位置，也有可能不属于山脉的一部分
• 状态3：当前数字大于下一数字：A[i] > A[i+1]，这种情况，这个数字可能会是一条山脉的右半组成部分

  且要构成一条山脉，需要先增后减，我们可以定义一个 temp 来表示组成一个山脉的数字个数，初始为 0，当遇到状态1和状态3时，temp 都会加 1，再定义一个 decrease 来标识对于一串连续的数字，是否出现了递减的部分。

  注意到，一条山脉只会在遇到以下三种情况时结束：

• 结束1：当前数字处于递减状态（状态1）且遇到数组末尾
• 结束2：前面数字是处于递减状态（状态3），而当前数字处于递增状态（状态1）
• 结束3：前面数字处于递减状态（状态3），当前数字处于平缓状态（状态2）

具体操作可结合代码和注释来理解

C代码如下：

int longestMountain(int* A, int ASize){
    if (ASize < 3) {
        return 0;
    }

    bool decrease = false;
    int i, max = 0, temp = 0;

    for (i = 0; i < ASize-1; i++) {
        // 若处于递增状态
        if (A[i + 1] > A[i]) {
            // 结束情况2：前面数字处于递减状态，而当前处于递增状态
            if (decrease) {
                decrease = false;
                max = fmax(max, temp + 1); // 算上当前的数字： temp + 1
                temp = 0; 
            } 
            temp++;
        } else if (A[i + 1] == A[i]) {
            // 结束情况2：前面数字处于递减状态，当前数字处于平缓状态
            if (decrease) {
                decrease = false;
                max = fmax(max, temp + 1);
            }
            temp = 0;
        } else if (temp > 0){
            decrease = true;
            temp++;
            // 结束情况1：当前数字处于递减状态，而遇到了数组末尾
            if (i == ASize - 2) {
                max = fmax(max, temp + 1);
            }
        }
    }

    return max;
}

解法2：动态规划

参考官方解答