题目描述

给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

• A.length >= 3
• 在 0 < i < A.length - 1 条件下，存在 i 使得：
  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[A.length - 1]

样例

输入：[2,1]
输出：false

输入：[3,5,5]
输出：false

输入：[0,3,2,1]
输出：true

注意

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

算法

(枚举) $O(n)$

1. 判定 A 的长度是否小于 3；
2. 从头开始找到第一个下降的位置 pivot，如果途中发现了相等的元素或者没有下降的位置，则返回 false；
3. 从 pivot 开始判定到结尾是否都是严格下降的；

时间复杂度

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

C++ 代码

class Solution {
public:
    bool validMountainArray(vector<int>& A) {
        int n = A.size();
        if (n < 3)
            return false;

        int pivot = -1;
        for (int i = 1; i < n; i++) {
            if (A[i - 1] == A[i])
                return false;
            else if (A[i - 1] > A[i]) {
                if (i == 1)
                    return false;
                pivot = i - 1;
                break;
            }
        }

        if (pivot == -1)
            return false;

        for (int i = pivot + 1; i < n; i++)
            if (A[i - 1] <= A[i])
                return false;

        return true;
    }
};