有效的山脉数组，怎么求？

添加新题啦，本题是一道双指针的经典应用，感受一下吧!

有效的山脉数组力扣题目链接：https://leetcode-cn.com/problems/valid-mountain-array/

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

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

思路

判断是山峰，主要就是要严格的保存左边到中间，和右边到中间是递增的。

这样可以使用两个指针，left和right，让其按照如下规则移动，如图：

注意这里还是有一些细节，例如如下两点：

• 因为left和right是数组下表，移动的过程中注意不要数组越界
• 如果left或者right没有移动，说明是一个单调递增或者递减的数组，依然不是山峰

C++代码如下：

 
 
 
 

  
  
  
  
class Solution { 
  
  
  
  
public: 
  
  
  
  
    bool validMountainArray(vector& A) { 
  
  
  
  
        if (A.size() < 3) return false; 
  
  
  
  
        int left = 0; 
  
  
  
  
        int right = A.size() - 1; 
  
  
  
  
 
  
  
  
  
        // 注意防止越界 
  
  
  
  
        while (left < A.size() - 1 && A[left] < A[left + 1]) left++; 
  
  
  
  
 
  
  
  
  
        // 注意防止越界 
  
  
  
  
        while (right > 0 && A[right] < A[right - 1]) right--; 
  
  
  
  
 
  
  
  
  
        // 如果left或者right都在起始位置，说明不是山峰 
  
  
  
  
        if (left == right && left != 0 && right != A.size() - 1) return true; 
  
  
  
  
        return false; 
  
  
  
  
    } 
  
  
  
  
}; 
 
 
 
 

如果想系统学一学双指针的话， 可以看一下这篇双指针法：总结篇!

其他语言版本

Java

 
 
 
 

  
  
  
  
class Solution { 
  
  
  
  
    public boolean validMountainArray(int[] arr) { 
  
  
  
  
        if (arr.length < 3) { // 此时，一定不是有效的山脉数组 
  
  
  
  
            return false; 
  
  
  
  
        } 
  
  
  
  
        // 双指针 
  
  
  
  
        int left = 0; 
  
  
  
  
        int right = arr.length - 1; 
  
  
  
  
        // 注意防止指针越界 
  
  
  
  
        while (left + 1 < arr.length && arr[left] < arr[left + 1]) { 
  
  
  
  
            left++; 
  
  
  
  
        } 
  
  
  
  
        // 注意防止指针越界 
  
  
  
  
        while (right > 0 && arr[right] < arr[right - 1]) { 
  
  
  
  
            right--; 
  
  
  
  
        } 
  
  
  
  
        // 如果left或者right都在起始位置，说明不是山峰 
  
  
  
  
        if (left == right && left != 0 && right != arr.length - 1) { 
  
  
  
  
            return true; 
  
  
  
  
        } 
  
  
  
  
        return false; 
  
  
  
  
    } 
  
  
  
  
} 
 
 
 
 

网页标题：有效的山脉数组，怎么求？
当前路径：http://www.hantingmc.com/qtweb/news37/345037.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联