LeetCode--941. 有效的山脉数组（C++描述）

痛定思痛。 2022-09-16 15:30 164阅读 0赞

// Source : https://leetcode-cn.com/problems/valid-mountain-array/  
// Date : 2021-10-22

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
给定一个整数数组 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\]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2w5peg5LiA55So5piv5Lmm55Sf_size_12_color_FFFFFF_t_70_g_se_x_16]

示例 1：

输入：arr = \[2,1\]  
输出：false  
示例 2：

输入：arr = \[3,5,5\]  
输出：false  
示例 3：

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

提示：

1 <= arr.length <= 104  
0 <= arr\[i\] <= 104

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
题目分析： 山峰数组，需要最值左右两侧的值依次递减，因此找到最大值之后从两侧开始向中间遍历即可，利用计数器记录  
高低子表的符合条件的元素个数，如果加起来是表长则说明符合山峰数组，返回true即可。  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

class Solution {
        
    public:
        bool validMountainArray(vector<int>& arr) {
        
            vector<int>::iterator biggest = max_element(begin(arr), end(arr));
            int max_index = distance(begin(arr), biggest);
            //如果最值多次出现，直接返回错误即可
            for(int i = 0;i < arr.size();++i)
                if(arr[i] == *biggest && i != max_index)
                    return false;
            //计数器从0开始是为了满足下标
            int low_count = 0;
            int high_count = 1;    
            if(max_index == 0 || max_index == arr.size() - 1)
                return false;
            //从头和尾向中间遍历，看看是否满足题意
            for(int low = 0;low < max_index; ++low)
                if(arr[low] < arr[low + 1])
                    low_count++;    
            for(int high = arr.size() - 1;high > max_index;--high)
                if(arr[high] < arr[high - 1])
                    high_count++;    
            //看高低子表的长度和是否等于表长
            if(low_count + high_count == arr.size())
                return true;
            else
                return false;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2w5peg5LiA55So5piv5Lmm55Sf_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ff2cec7a2b34490a8e6e19c8a9aa149a.png