941.有效的山脉数组

发表于： 分类于：
字数： 723 阅读：≈ 2分钟

⛰ 941.有效的山脉数组

给定一个整数数组 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]

思路

基本思想

能找到一个一个数，这个数的右边和左边都成递减趋势，并且是严格递减，而不能存在相等的情况

img

所以需要找到变化的点，也就是找到先上升在下降的点，上升时严格上升，递减时严格递减

在转折点之前必须严格递增，转折点之后必须严格递减，并且转折点之后严格递减，所以需要模拟严格递增的过程，一旦出现递减，说明找到了转折点，并且需要判断转折点在哪

递减的过程中不能出现递增或者想等的情况，模拟上述过程即可

执行流程

  1. 为了递增过程的连续性，先使用一个while循环模拟递增的过程
  2. 递增过程中一旦出现相等，直接返回false，一旦出现递减，说明找到了转折点
  3. 判断转折点是不是开头或末尾，防止[2,1]或者[1,2,3]的情况
  4. 递减过程中一旦出现相等，直接返回false，一旦出现递增，也返回false
  5. 遍历到了末尾说明一直符合要求，此时才返回true

代码

根据以上分析，得出以下代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if(arr.size()<3)
            return false;
        int i=0;
        int max=INT_MIN;  
        while(i<arr.size()-1){//严格递增的代码
            if(arr[i+1]==arr[i]){
                return false;
            }
            else if(arr[i+1]<arr[i])
            {
                break;
            }
            i++;//严格递增就i++
        }//到这里就是找到了转折点,并且之前的元素都是严格递增
        if(i==0||i==arr.size()-1)
            return false;
        while(i<arr.size()-1){
            if(arr[i+1]>=arr[i])//一旦出现等于或者递增的情况，直接返回false
                return false;
           i++;//严格递减就i++
        }
        return true;
    }
};

总结

需要找到这个转折点，从而判断两端是否是严格递增递减