Crying 与爬山 - 题解

标签与难度

标签: 模拟, 数组, 遍历, 入门, 条件判断难度: 800

题目大意喵~

你好呀，未来的算法大师！Crying 正在研究爬山，我们来帮帮他吧，喵~

这道题是说，我们有一条长长的山路，它的长度是 $n$ 。我们知道路上从第 $1$ 个点到第 $n$ 个点的每一个点的高度，可以看成一个函数 $f(x)$ 的值。

Crying 对一种特殊的地形很感兴趣，他称之为“极值点”。一个点 $x$ (必须在 $2$ 到 $n-1$ 之间) 能被称为“极值点”，当且仅当它同时满足两个条件：

它比它左边的点 $x-1$ 要低，也就是 $f(x-1) > f(x)$ 。
它也比它右边的点 $x+1$ 要低，也就是 $f(x) < f(x+1)$ 。

简单来说，就是一个小小的“山谷”或者“凹陷”地形啦！我们的任务就是，看着给出的整条山路的高度图，数一数一共有多少个这样的“极值点”，然后告诉 Crying，喵~

比如，如果高度是 [3, 1, 5]，那么中间的点（值为1）就比左边的3低，也比右边的5低，所以它就是一个极值点！

解题思路分析

喵哈~！这道题其实超级直白的喵！它是在考验我们是不是能把文字描述准确地转换成代码逻辑呢。

首先，我们来仔细看看“极值点”的定义：对于一个点 $x$ ，它要是极值点，必须满足 $f(x-1) > f(x) < f(x+1)$ 。

这个定义给了我们两个非常重要的信息：

条件: 判断一个点是不是极值点，需要看它和它左右紧邻的两个点的高度。
范围: 题目明确说了， $x$ 的取值范围是 $[2, n-1]$ 。为什么呢？因为如果 $x=1$ ，它没有左边的点 $x-1$ ；如果 $x=n$ ，它没有右边的点 $x+1$ 。没有两个邻居，就没法形成“山谷”啦，所以我们只需要检查中间的那些点就可以啦，喵~

那么，解题的思路就非常清晰了：

先把所有 $n$ 个点的高度值都读进来，用一个数组或者 vector 存好。这个数组就像是我们手中的地图，记录了整条山路。
我们设置一个计数器 count，初始值为 0。这个计数器用来记录我们找到了多少个“小山谷”。
接下来，我们就要开始“巡山”啦！我们用一个循环，遍历所有可能成为极值点的 $x$ $x$ 。根据题目的范围 $[2, n-1]$ $[2, n - 1]$ ，我们的循环就要从第 2 个点一直检查到第 $n-1$ $n - 1$ 个点。
- 注意喵！ 在编程时，数组的下标通常是从 0 开始的。所以，第 $x$ 个点对应的数组下标是 $x-1$ 。那么，我们要检查的点 $x$ 从 $2$ 到 $n-1$ ，对应的数组下标就是从 $1$ 到 $n-2$ 。
在循环的每一步，我们检查当前的点 i (对应函数点 $x=i+1$ ) 是否满足条件 f[i-1] > f[i] && f[i] < f[i+1]。
如果这个点满足条件，说明我们找到了一个“极值点”！太棒了！让我们的计数器 count 增加 1。
当循环结束，我们就检查完了所有可能的点。这时候计数器 count 的值，就是最终的答案啦！

你看，是不是就像在地图上一个个地检查标记点一样简单呢？只要细心一点，不要搞错循环的范围和判断的条件，就一定能做对的，加油喵！

代码实现

这是我根据上面的思路，精心为你准备的一份 C++ 代码，注释超详细的哦！

cpp

#include <iostream>
#include <vector>
#include <numeric> // 虽然这个题目用不到，但引入一些常用库是个好习惯喵~

int main() {
    // 使用这两行代码可以让输入输出更快，处理大数据时很有用哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    // 读取n，就是我们山路的总长度啦~
    std::cin >> n;

    // 如果点的数量小于3，是不可能形成 f(x-1) > f(x) < f(x+1) 这样的结构的
    // 因为至少需要3个点才能有一个点被夹在中间嘛~
    if (n < 3) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // 用一个vector来存放每个点的高度值，喵~
    std::vector<int> f(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> f[i];
    }

    int extreme_points_count = 0; // 这是我们的计数器，用来数找到了多少个极值点

    // 遍历所有可能的极值点，注意范围哦！
    // 题目要求 x 在 [2, n-1] 之间，对应到0-based的数组下标就是 [1, n-2]
    for (int i = 1; i < n - 1; ++i) {
        // f[i] 是当前点，f[i-1] 是左边的点，f[i+1] 是右边的点
        // 这就是题目给的'山谷'的定义！
        if (f[i - 1] > f[i] && f[i] < f[i + 1]) {
            // 找到一个，计数器就+1，耶！
            extreme_points_count++;
        }
    }

    // 最后，把结果打印出来~
    std::cout << extreme_points_count << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 我们只需要一个循环来遍历所有可能的极值点。这个循环从数组下标 1 运行到 n-2，总共执行了 $n-2$ 次。所以，总的时间消耗和点的数量 $N$ 是线性相关的，记为 $O(N)$ 。对于这道题的数据量来说，是飞快飞快的~
空间复杂度: $O(N)$ 我们用了一个 vector (或者数组) f 来存储 $N$ 个点的高度值。这个 vector 的大小和输入规模 $N$ 成正比。除此之外，我们只用到了几个额外的变量（如 n, extreme_points_count），它们占用的空间是常数级别的。所以，主要的额外空间开销就是存储高度的数组，空间复杂度为 $O(N)$ 。

知识点总结

这道题虽然简单，但也是一次很好的练习机会呢，喵~

问题解读能力: 核心是准确理解题目中“极值点”的定义，不遗漏任何一个条件。
数组/Vector 的使用: 学习如何用数组或 vector 来存储一个序列，并通过下标访问其中的元素。
循环与边界控制: 这是算法题中最最重要的一环！正确地确定循环的起始和结束条件（比如本题中的 for (int i = 1; i < n - 1; ++i)) 是避免程序出错（如数组越界）的关键。
条件判断: 使用 if 语句和逻辑与运算符 && 来实现复杂的条件判断，这是编程的基本功。
模拟思想: 很多题目并不需要高深的算法，只需要按照题目的规则一步步执行下来即可。这种“直接模拟”的思路是解决问题的基础。

希望这篇题解能帮到你，继续加油哦！算法的世界还有更多有趣的冒险在等着我们呢，喵~！

Crying 与爬山 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​