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]

示例 1：

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

示例 2：

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

示例 3：

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

思路：线性扫描

• 按照题目模拟即可，我们从数组最左侧开始向右扫描
• 直到找到第一个不满足A[i]<A[i+1] 的下标 i ,那么 i 就是这个数组的最高点下标
• 如果 i = 0 或者不存在这样的 i (即整个数组单调递增)，那么就返回false
• 否则 从 i 开始继续向右扫描，判断接下来的下标 j 是否都满足 A[j]>A[j+1] ，若都满足返回true ,不满足返回false.

class Solution {
    public boolean validMountainArray(int[] A) {
        int n = A.length;
        int i = 0;

        // 检查最高点左半部分
        while(i + 1 < n && A[i] < A[i + 1]){
            i++;
        }

        // 最高点不能是数组的第一个位置或者最后一个位置
        if(i == 0 || i == n - 1){
            return false;
        }

        // 检查最高点后半部分
        while(i + 1 < n && A[i] > A[i + 1]){
            i++;
        }

        // 判断是否正确走到了数组最后
        return n - 1 == i;
    }
}

复杂度分析：

• 时间复杂度：O(n) 扫描一遍数组所需要的时间
• 空间复杂度：O(1)

打赏