leetcode941.有效的山脉数组

题目

给定一个整数数组 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 <= 104
• 0 <= arr[i] <= 104

解答

• 暴力解法

首先获取数组中最大的数字以及下标，然后对下标进行判断，符合条件（数组大小超过2并且最大值不是数组的第一个元素或者最后一个元素）时进行第二次循环，循环时判断相邻元素是否满足递增或者递减的关系。C++实现代码如下：

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        // 得到最大值
        int maxNum = -1;
        int maxIndex = -1;
        int n = arr.size();
        if (n < 3) return false;
        for (int i = 0; i < n; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
                maxIndex = i;
            }
        }
        // 得到最大值后进行一部分判断然后进行循环
        if (maxIndex == n-1 || maxIndex == 0) return false;

        for (int i = 0; i < maxIndex; i++) {
            if (arr[i] >= arr[i + 1]) return false;
        }
        for (int i = maxIndex; i < n - 1; i++) {
            if (arr[i] <= arr[i + 1]) return false;
        }
        return true;
    }
};

• 只扫描一次的解法

class Solution {
public:
    bool validMountainArray(vector<int>& A) {
        int n = A.size();
        
        // 山脉数组必须至少有3个元素
        if (n < 3) {
            return false;
        }
        
        int i = 0;
        
        // 从左侧递增部分开始扫描
        while (i < n - 1 && A[i] < A[i + 1]) {
            i++;
        }
        
        // 如果i是数组的第一个元素或者最后一个元素，说明没有递增或递减的足够元素
        if (i == 0 || i == n - 1) {
            return false;
        }
        
        // 扫描递减部分
        while (i < n - 1 && A[i] > A[i + 1]) {
            i++;
        }
        
        // 如果i已经到达数组的末尾，说明是有效的山脉数组
        return i == n - 1;
    }
};