你好！我是金牌教练。寻找峰值这道题非常有趣，它完美诠释了 “局部性质决定全局存在” 的数学思想。

在 NOI 竞赛中，虽然 $O(n)$ 的线性扫描通常能过 $10^5$ 的数据，但掌握 $O(\log n)$ 的二分法是区分普通选手与顶尖选手的关键，因为在更复杂的问题中（如高维峰值查找），线性复杂度会彻底失效。

版本 1：暴力扫描版 (Linear Scan)

思路提示： 最直截了当的方法。遍历数组，检查每一个元素是否满足比左边大且比右边大。 由于题目规定 $nums[-1] = nums[n] = -\infty$，所以：

1. 如果 $n=1$，索引 0 就是峰值。
2. 检查 $nums[0]$ 是否大于 $nums[1]$。
3. 检查 $nums[n-1]$ 是否大于 $nums[n-2]$。
4. 中间元素需满足 $nums[i] > nums[i-1]$ 且 $nums[i] > nums[i+1]$。

复杂度分析：

• 时间复杂度：$O(n)$。最坏情况下需要遍历整个数组。
• 空间复杂度：$O(n)$（存储输入数据）。

/*
 * 暴力扫描版：严格按照峰值定义检查
 * 易错点：数组越界处理（尤其是 0 和 n-1 处）
 */
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    // 特判：只有一个元素
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < n; i++) {
        bool left_ok = (i == 0) || (nums[i] > nums[i - 1]);
        bool right_ok = (i == n - 1) || (nums[i] > nums[i + 1]);
        
        if (left_ok && right_ok) {
            cout << i << endl;
            return 0; // 只要找到一个就退出
        }
    }
    return 0;
}

版本 2：线性爬坡版 (Linear Climb)

思路提示： 由于 $nums[-1] = -\infty$，只要数组开始增长（$nums[i] < nums[i+1]$），我们就处于上坡。 第一个满足 $nums[i] > nums[i+1]$ 的位置 $i$，一定是一个峰值。 为什么？因为既然它是第一个满足该条件的，说明它之前的元素都是递增的（即 $nums[i] > nums[i-1]$），而现在它又比右边大，它就是峰。

复杂度分析：

• 时间复杂度：$O(n)$。虽然比版本 1 简洁，但本质仍是线性。
• 空间复杂度：$O(1)$（不计数组）。

/*
 * 线性爬坡版：寻找第一个下降点
 * 逻辑：只要在上升，就还没到峰顶。一旦下降，当前点就是峰。
 */
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    for (int i = 0; i < n - 1; i++) {
        // 如果当前点比右边大，由于前面一直在上升，这里就是峰值
        if (nums[i] > nums[i + 1]) {
            cout << i << endl;
            return 0;
        }
    }
    
    // 如果一直没找到，说明数组单调递增，最后一个元素是峰
    cout << n - 1 << endl;
    return 0;
}

版本 3：最优解 - 二分查找版 (Binary Search)

思路提示： 版本 2 的“爬坡”思想可以被二分加速。

1. 取中点 mid。
2. 比较 nums[mid] 和 nums[mid+1]。
3. 如果 nums[mid] < nums[mid+1]，说明右侧必有峰值（上坡必有顶）。
4. 如果 nums[mid] > nums[mid+1]，说明左侧（含 mid）必有峰值。

复杂度分析：

• 时间复杂度：$O(\log n)$。对于 $10^5$ 数据，仅需 17 次比较。
• 空间复杂度：$O(1)$。

/*
 * 二分查找版：NOI 满分标准代码
 * 关键点：利用局部单调性缩小搜索范围
 * 易错点：循环条件 L < R 以及 L = mid + 1 的细节
 */
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 提高 IO 速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    int left = 0, right = n - 1;
    
    // 使用左闭右开或左闭右闭逻辑。这里采用 L < R，最终 L == R 即为答案
    while (left < right) {
        // 防止溢出的中点写法
        int mid = left + (right - left) / 2;
        
        // 核心判定：往高处走
        if (nums[mid] < nums[mid + 1]) {
            // 右边更高，说明峰值在右侧区间 (不含 mid)
            left = mid + 1;
        } else {
            // 左边更高或相等(虽然题目说不等)，说明峰值在左侧区间 (含 mid)
            right = mid;
        }
    }

    // 循环结束时，left == right，指向其中一个峰值
    cout << left << endl;

    return 0;
}

时间复杂度优化建议与总结

1. 二段性分析： 通常二分查找需要全局有序，但本题告诉我们，只要能通过某种判定（相邻元素大小）排除掉一半不可能包含特定解（其中一个峰值）的区间，就可以使用二分。这在处理复杂几何问题（如三分法找极值）时非常有用。

2. 边界保护： 在版本 3 中，mid = left + (right - left) / 2。 当 left < right 时，mid 永远能够取到 left 但永远取不到 right。 这意味着 mid + 1 永远不会导致数组下标越界（最大为 right）。这是竞赛中处理边界的小技巧。

3. 数据范围注意事项： 题目中 $nums[i]$ 的范围达到了 $2^{31}-1$，这是 int 的极限。在进行比较时没问题，但如果你在代码中涉及 nums[i] + nums[j] 这种操作，必须开启 long long，否则会溢出导致逻辑错误。

4. 优化建议： 对于 $N=10^5$ 的规模，std::vector 的分配耗时可以忽略。但如果 $N$ 达到 $10^6$ 以上，建议使用静态数组 int a[1000005]，以获得更极致的运行速度。

总结：这道题考察的是你对二分本质的理解——二分不是为了找“值”，而是为了通过“判定”不断缩小“候选区间”。加油！