LeetCode 941.有效的山脉数组

题目描述

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

提示

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

输入输出示例

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

示例 2
输入：[3,5,5]
输出：false

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

题解

这道题本身没有任何需要特别注意的点，最坏情况下也只是多提交几次补全所有情况。

对于这种题目，应该思考的是，如何在第一次尽可能地覆盖所有可能。首先读题：要求数组至少有 3 个元素，并且先是一个严格递增部分，而后是一个严格递减部分。

第一个限定条件很容易确定：至少有三个元素。进行一个长度判断即可
第二个限定条件是：存在严格递增和严格递减部分。也即保证第一个小于第二个，倒数而第二个大于倒数第一个（由于上一个条件已经确保至少三个，因此这里不会溢出）。
第三个限定条件是：严格递增(减)。也即不存在相邻的相等数（可能在上升和下降部分重复出现），因此在遍历过程发现相同应该直接结束
最后就是正常的遍历过程，由于只需要相邻数对比，因此只需要缓存上一个数。同时由于前两个数已经遍历，因此可以直接从第二个数开始判断。

代码

bool validMountainArray(int* A, int ASize){
    if (ASize < 3) return false; // 高度足够
    if (A[0] >= A[1] || A[ASize-2] <= A[ASize-1]) return false; // 必定存在上升过程和下降过程

    bool up = true;
    int lst = A[1];
    for (int i = 2; i<ASize; ++i){
        int now = A[i];
        if (now == lst) return false; // 禁止相等
        if (up) {
            if (now < lst) up = false;
        } else {
            if (now > lst) return false;
        }
        lst = now;
    }
    return true;
}