LeetCode 941. Valid Mountain Array (有效的山脉数组)

发布时间：2020-12-14 02:03:52 所属栏目：Linux 来源：网络整理

导读：题目标签：Array ? 题目给了一组int array A，让我们判断它是否是一个山脉数组。 ? 山脉数组一定要有一个最高值，然后要同时有山坡和下坡。 ? 想法是，从左边开始依次比较两个数字，int[0] int[1].... 如果是上坡，继续寻找，如果遇到了下坡，停止，这样就

题目标签：Array

? 题目给了一组int array A，让我们判断它是否是一个山脉数组。

? 山脉数组一定要有一个最高值，然后要同时有山坡和下坡。

? 想法是，从左边开始依次比较两个数字，int[0] int[1].... 如果是上坡，继续寻找，如果遇到了下坡，停止，这样就找到了最高点。

? 从右边也是同样的操作。

? 然后排除只有上坡的，或者只有下坡的情况。

? 最后比较一下，左边找到的最高点和右边找到的最高点是否是同一个点。

? 具体看code。

Java Solution:

Runtime beats 99.95%?

完成日期：03/05/2019

关键点：从左右两个方向各自找最高点

class Solution 
{
    public boolean validMountainArray(int[] A) 
    {
        if(A.length < 3)
            return false;
        
        int left = 0;
        int right = A.length - 1;
    
        // from left: climb the hill until the highest reached
        while(left + 1 < A.length && A[left] < A[left + 1])
            left++;
        // from right: climb the hill until the highest reached
        while(right - 1 > 0 && A[right] < A[right - 1])
            right--;
        
        
        if(left == A.length - 1) // only uphill
            return false;
        else if(right == 0) // only downhill
            return false;
        
        
        return left == right;
    }
}

参考资料：N/A

LeetCode 题目列表 -?LeetCode Questions List

题目来源：https://leetcode.com/

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!