题目

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

  解题方法

  双指针

  左右指针分别从两侧“爬山”，最终判断是否相遇即可，注意左右指针的移动范围。
  时间复杂度O(n)，空间复杂度O(1)。
  C++代码：

  class Solution {
  public:
    bool validMountainArray(vector<int>& arr) {
        int n = arr.size();
        if(n<3) return false;
        int l=0, r=n-1;
        while(l<n-2 && arr[l+1]>arr[l]) l++;
        if(arr[l+1]==arr[l])    return false;
        while(r>1 && arr[r-1]>arr[r])   r--;
        return r==l;
    }
  };