GESP C++四级算法题解析：线性扫描法解决'山之谷'问题

1. 题目背景与需求解析

这道编程题来自GESP（青少年编程能力等级考试）2026年3月C++四级认证的第三部分编程题，题目名为"山之谷"。作为认证考试中的编程实践环节，这类题目通常考察考生对基础算法、数据结构以及编程思维的掌握程度。

从题目名称"山之谷"可以推测，这很可能是一道与地形分析或序列处理相关的题目。在编程竞赛和算法题中，"山谷"一般指代序列中先递减后递增的连续元素组合。这类题目往往要求考生能够：

1. 正确理解并抽象问题模型
2. 设计合理的算法解决方案
3. 编写高效且正确的代码实现
4. 处理各种边界条件和特殊情况

2. 问题建模与算法设计

2.1 问题定义

假设题目给出一个整数数组，表示一系列山的高度。我们需要找出所有符合条件的"山谷"。一个标准的山谷定义应该满足以下条件：

1. 存在三个连续的元素：arr[i], arr[j], arr[k]
2. 满足i < j < k
3. arr[i] > arr[j]且arr[j] < arr[k]
4. 山谷长度为k - i + 1

例如，对于数组[5, 2, 8]，元素5、2、8就构成了一个山谷，因为5>2<8。

2.2 算法选择

解决这类序列模式识别问题，常见的算法思路包括：

1. 线性扫描法：遍历数组一次，记录可能的谷底位置，然后向两侧扩展
2. 双指针法：使用左右指针标记山谷的起始和结束位置
3. 动态规划：记录上升和下降的趋势变化

对于四级考试难度，线性扫描法应该是最合适的选择，因为：

• 时间复杂度O(n)，效率高
• 实现简单，代码量少
• 容易理解和调试

2.3 核心算法步骤

1. 初始化变量记录当前找到的最大山谷长度
2. 遍历数组，寻找所有可能的谷底（即比左右邻居都小的元素）
3. 对于每个谷底，向左右两侧扩展，直到不再满足递减/递增条件
4. 计算当前山谷长度，更新最大值
5. 最终输出最大的山谷长度

3. 代码实现与解析

3.1 基础实现框架

cpp复制#include <iostream>
#include <vector>
using namespace std;

int findLongestValley(const vector<int>& arr) {