解题思路

大家见过大海里的浪吗？一浪接一浪，最高的那个浪头，就是"浪尖"。

这道题里，我们把一列数想象成一排高低不同的海浪：

• 有的数比它左边的数高，也比它右边的数高，它就像大海里最高的那个浪头，比两边的浪都高，这样的数就叫浪尖数。
• 但是，第一个数和最后一个数不算！因为它们在最边上，只有一边有邻居，没有"左右两个邻居"，所以不可能当浪尖。

所以判断一个数是不是浪尖数，要看三个条件同时满足：

1. 它比左边的数大；
2. 它比右边的数大；
3. 它不是第一个，也不是最后一个（有左右两个邻居）。

我们举个例子。样例输入是：

5
1 3 2 4 1

数组存好后是：a[0]=1, a[1]=3, a[2]=2, a[3]=4, a[4]=1。

我们一个个看中间的数（跳过第一个 a[0] 和最后一个 a[4]）：

• 看 a[1]=3：左边是 a[0]=1，右边是 a[2]=2。3 比 1 大，3 也比 2 大，是浪尖数！
• 看 a[2]=2：左边是 a[1]=3，右边是 a[3]=4。2 比 3 小，不是浪尖数。
• 看 a[3]=4：左边是 a[2]=2，右边是 a[4]=1。4 比 2 大，4 也比 1 大，是浪尖数！

所以 3 和 4 是两个浪尖数，答案输出 2。

再想一想：如果只有 3 个数，比如 1 2 3，中间的 2 比左边的 1 大，但是比右边的 3 小，两边都要大才行，所以它不是浪尖数，答案输出 0。

注意数组下标从 0 开始：第一个数是 a[0]，最后一个数是 a[n-1]。中间能当浪尖的数是从 a[1] 到 a[n-2]，所以循环要从 i=1 一直走到 i=n-2。

参考代码

// P377 浪尖数
// 数组里有些数比它左右相邻的两个数都大，这样的数叫"浪尖数"。
// 第一个和最后一个数没有左右两个邻居，不算。
// 求数组里一共有多少个浪尖数。

#include <iostream>
using namespace std;

int main() {
    int n;          // n 表示数组里有多少个数
    int a[105];     // 数组 a 用来存这 n 个数（n <= 100，开 105 留余量）
    int cnt = 0;    // cnt 用来数一数浪尖数有几个

    // 第一步：读入 n 和 n 个数
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 第二步：找浪尖数
    // 浪尖数必须有左右两个邻居，所以从 a[1] 检查到 a[n-2]，
    // a[0]（第一个）和 a[n-1]（最后一个）都不检查。
    for (int i = 1; i <= n - 2; i++) {
        // 这个数要比左边的数大，还要比右边的数大，才是浪尖数
        if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
            cnt++;    // 找到一个浪尖数，计数器加 1
        }
    }

    // 第三步：输出浪尖数的个数
    cout << cnt << endl;

    return 0;
}

复杂度分析

• 时间复杂度：O(n)。只需要从 a[1] 到 a[n-2] 把每个数检查一遍，循环 n 次左右，n 最大只有 100，非常快。
• 空间复杂度：O(n)。用一个数组 a 把 n 个数都存了下来，所以占用空间和 n 成正比。n 最大 100，占的空间非常小。

（注：其实判断浪尖数只需要比较相邻的数，如果能一边读一边处理，也可以不用存整个数组，但对这道题来说，先把数存进数组再统一检查，思路更清楚，小朋友也更好理解。）