题解 | #求峰谷点数#

题目链接

求峰谷点数

题目描述

这是一个函数实现题。你需要实现一个 countPeakPoint 函数，该函数接受一个由正整数构成的序列 a 作为参数。

如果序列中某个元素 a[i] 满足 a[i-1] < a[i] > a[i+1]，则称 a[i] 为一个峰点。
如果序列中某个元素 a[i] 满足 a[i-1] > a[i] < a[i+1]，则称 a[i] 为一个谷点。

你需要计算并返回序列中峰点和谷点的总数量。

注意：

峰点和谷点的定义只对序列内部的元素（即非首尾元素）有效。
平台负责处理输入输出，你只需实现函数逻辑。

示例:

输入: [1, 1, 4, 5, 1, 4] (由平台传入你的函数)
你的函数应返回: 2
说明: a[3]=5 是一个峰点 (4 < 5 > 1)，a[4]=1 是一个谷点 (5 > 1 < 4)。总数为 2。

解题思路

本题的目标是统计数组中满足特定局部极值条件的元素个数。解法非常直接，只需遍历数组并检查每个元素是否符合峰点或谷点的定义即可。

处理边界情况: 根据定义，一个元素需要有前一个和后一个邻居才能被判断为峰点或谷点。这意味着数组的第一个和最后一个元素永远不可能是峰点或谷点。因此，如果数组的长度小于 3，就不可能存在任何峰点或谷点，可以直接返回 0。
遍历数组: 我们需要遍历所有可能成为峰点或谷点的元素。这些元素的索引范围是从 1 到 n-2（其中 n 是数组的长度）。
检查条件: 在循环中，对于当前索引 i，我们检查 a[i] 与其左右邻居 a[i-1] 和 a[i+1] 的关系：
- 峰点条件: 如果 a[i-1] < a[i] 并且 a[i] > a[i+1]，则找到了一个峰点。
- 谷点条件: 如果 a[i-1] > a[i] 并且 a[i] < a[i+1]，则找到了一个谷点。
计数: 初始化一个计数器 count 为 0。每当找到一个峰点或谷点时，就将计数器加一。
返回结果: 遍历结束后，count 中存储的就是峰点和谷点的总数，将其作为函数返回值即可。

代码

注意：以下是你需要提交的全部内容，即在牛客网给定的模板中填写的代码。

c++
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求序列a中的峰、谷点的个数
     * @param a int整型vector 序列a
     * @return int整型
     */
    int countPeakPoint(std::vector<int>& a) {
        int n = a.size();
        if (n < 3) {
            return 0;
        }
        
        int count = 0;
        for (int i = 1; i < n - 1; ++i) {
            bool is_peak = (a[i] > a[i - 1]) && (a[i] > a[i + 1]);
            bool is_valley = (a[i] < a[i - 1]) && (a[i] < a[i + 1]);
            if (is_peak || is_valley) {
                count++;
            }
        }
        return count;
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求序列a中的峰、谷点的个数
     * @param a int整型一维数组 序列a
     * @return int整型
     */
    public int countPeakPoint(int[] a) {
        int n = a.length;
        if (n < 3) {
            return 0;
        }
        
        int count = 0;
        for (int i = 1; i < n - 1; i++) {
            boolean isPeak = a[i] > a[i - 1] && a[i] > a[i + 1];
            boolean isValley = a[i] < a[i - 1] && a[i] < a[i + 1];
            if (isPeak || isValley) {
                count++;
            }
        }
        return count;
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 求序列a中的峰、谷点的个数
# @param a int整型一维数组 序列a
# @return int整型
#
class Solution:
    def countPeakPoint(self, a: List[int]) -> int:
        n = len(a)
        if n < 3:
            return 0
        
        count = 0
        for i in range(1, n - 1):
            is_peak = a[i] > a[i-1] and a[i] > a[i+1]
            is_valley = a[i] < a[i-1] and a[i] < a[i+1]
            if is_peak or is_valley:
                count += 1
        
        return count

算法及复杂度

算法: 线性扫描/单次遍历。
时间复杂度: $\mathcal{O}(N)$ ，其中 $N$ 是序列 a 的长度。我们只需要对数组进行一次遍历，从索引 1 到 N-2。
空间复杂度: $\mathcal{O}(1)$ 。我们只使用了少数几个变量来存储计数值和循环索引，没有使用与输入规模成正比的额外空间。