折点计数

形式化题目

给定 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ，保证相邻两项不同。若某个中间位置 $a_i$ 满足前一段（ $a_{i-1}$ 到 $a_i$ ）与后一段（ $a_i$ 到 $a_{i+1}$ ）的增减方向相反，则称 $i$ 是折点。统计所有折点的个数。

思路

第 $i$ 天是否是折点，只取决于它和前一天、后一天的关系。

判断一个位置

记两个相邻差值：

d_1 = a_i - a_{i-1}, \qquad d_2 = a_{i+1} - a_i

先增后减： $d_1 > 0$ 且 $d_2 < 0$ ；
先减后增： $d_1 < 0$ 且 $d_2 > 0$ 。

两种情况都等价于 $d_1 \times d_2 < 0$ 。由于题目保证相邻两天销量不同， $d_1, d_2$ 都不为 $0$ ，乘积为负恰好表示方向相反。

扫描所有中间位置

端点 $i=1$ 和 $i=n$ 缺少完整的前后两天，不可能成为折点，因此只需扫描 $i = 2 \sim n-1$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:48
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
int sales[MAXN]; // 每天的销售量

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> sales[i];
    }

    int answer = 0;
    // 第 i 天是折点，当且仅当前一段与后一段的增减方向相反。
    // 相邻两天的销量保证不同，因此两个差值乘积为负就说明方向相反。
    for (int i = 2; i <= n - 1; i++) {
        int diff1 = sales[i] - sales[i - 1];
        int diff2 = sales[i + 1] - sales[i];
        if (diff1 * diff2 < 0) {
            answer++;
        }
    }
    cout << answer << '\n';
    return 0;
}

复杂度

时间：扫描每个中间位置做常数次比较，时间复杂度为 $O(n)$ 。
空间：需要保存全部 $n$ 个销量，空间复杂度为 $O(n)$ 。

总结

折点判断可以统一为相邻差值乘积的符号，峰值和谷值共用同一条判断。注意端点缺少前后两天，不能计入答案。

目录

形式化题目

思路

判断一个位置

扫描所有中间位置

代码

复杂度

总结