475，有效的山脉数组

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

The strongest person is the person who isn't scared to be alone.

强大的人不会惧怕孤独。

问题描述

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

提示：

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

从两边找

这题让判断一个数组是否是有效山峰数组，所谓有效山峰数组就是在数组中有且仅有一个最大值，并且最大值往前走是降序的，往后走也是降序的。

一种简单的解决方式就是使用两个变量left和right，我们也可以把它看做是两个指针，left从数组的前面开始，如果是升序的就一直找，直到遇到降序的时候停止，right从数组后面往前找，如果是升序的就一直找，直到遇到降序的时候停止。然后再判断left和right是否相等。如下图所示

来看下代码

 1public boolean validMountainArray(int[] A) {
 2    int len = A.length;
 3    int left = 0;
 4    int right = len - 1;
 5    //从左边往右边找，一直找到山峰为止
 6    while (left + 1 < len && A[left] < A[left + 1])
 7        left++;
 8    //从右边往左边找，一直找到山峰为止
 9    while (right > 0 && A[right - 1] > A[right])
10        right--;
11    //判断从左边和从右边找的山峰是不是同一个
12    return left > 0 && right < len - 1 && left == right;
13}

从一边找

从一边找的思路就是，先从左边开始找到山峰，然后再从山峰开始往右边下山，如果能走到数组的最后一个元素，说明是有效山峰。

 1public boolean validMountainArray(int[] A) {
 2    int len = A.length;
 3    int left = 0;
 4    //从左边往右边找，一直找到山峰为止
 5    while (left + 1 < len && A[left] < A[left + 1])
 6        left++;
 7    //如果数组一开始就是降序,比如[4,3,2,1],或者一直是升序的，
 8    //比如[1,2,3,4]都不能称为有效山峰
 9    if (left == 0 || left == len - 1)
10        return false;
11    //找到山峰之后然后下山
12    while (left + 1 < len && A[left] > A[left + 1])
13        left++;
14    //如果能走到山脚下，也就是走到数组的最后一个元素，就表示
15    //是有效山峰
16    return left == A.length - 1;
17}