LC 0941.Valid Mountain Array

题目描述

这是 LeetCode 上的 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]

示例 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

解答

方法一：模拟

根据条件，如果是山脉数组则其结构一定是先递增再递减，于是我们先遍历前面，找出最大值，然后判断后面的数是否递减，如果符合条件则为山脉数组，注意题目中不能存在相等的情况。

class Solution {
    public boolean validMountainArray(int[] arr) {
        int i = 0, max = -1;
        while (i < arr.length) {
            if (arr[i] <= max) {
                break;
            }
            max = arr[i++]; // 最后一次 i 会在最大值的后面一个位置
        }
        if (i == arr.length || i == 1) { // 如果最大值出现在数组两端则不是山脉数组
            return false;
        }
        while (i < arr.length) {
            if (arr[i] >= max) {
                return false;
            }
            max = arr[i++];
        }
        return true;
    }
}

• 时间复杂度：\(O(N)\)，其中 N 为 arr 的长度。

• 空间复杂度：\(O(1)\)。

每题一图