做序列处理题做到 201604-1 这道“折点计数100分【序列处理】”第一次看题我差点被“折点”两个字唬住。后来把题面读完才发现它问的不过是一个整数序列里有多少个“山峰”和“山谷”。给定 n 个整数从左到右排成一列凡是某个数同时严格大于左右两个邻居或者同时严格小于左右两个邻居这个位置就算一个折点。首尾两个元素没有两侧邻居一律跳过。这道题非常适合刚开始刷算法题的人也适合面试前用来快速恢复手感的老手。你不需要会动态规划不需要会排序只要把“严格相邻比较”这件事做对就能拿满分。1. 先搞清楚“折点”到底是什么意思1.1 题目输入与场景先看输入格式。第一行给一个正整数 n表示序列长度第二行给 n 个整数用空格隔开。比如7 5 4 2 6 3 1 2你完全可以把这串数想成某几天的气温、某门店的销量或者任何随时间变化的指标。题目没有要求你对这些数字的业务含义做推导所以不用想太多它就是一个数组。标准做法是把它们逐项读进 int 数组下标从 0 到 n-1然后逐项判断。这类“先给长度再给序列”的输入方式在很多认证考试和在线评测里都很常见。它的好处是方便一次性申请数组空间坏处是一旦 n 比较大你必须小心别在数组和循环范围上栽跟头。对本题而言n 的规模不会特别夸张开数组时多留几个空位就行不需要刻意做空间压缩。我一般习惯把数组长度定义成 n5避免下标访问越界时出现诡异错误。1.2 数学上的定义局部极大值或局部极小值“折点”这个词听起来像几何概念实际上离散序列里的折点就是局部极值点。对于三个相邻的数 a[i-1]、a[i]、a[i1]如果a[i] a[i-1] 并且 a[i] a[i1]那么 a[i] 是一个峰a[i] a[i-1] 并且 a[i] a[i1]那么 a[i] 是一个谷。无论是峰还是谷都算一个折点。换句话说只要中间这个数比它前后两个邻居都大或者都比它们小就满足条件。如果一个数前一个比它大、后一个比它小或者前一个比它小、后一个比它大那说明它只是在一条上升或下降趋势的中间位置并不是趋势转折点不算折点。用一个具体例子看一遍。序列 [5, 4, 2, 6, 3, 1, 2] 中下标 1 的 4左边 5 大于 4右边 2 小于 4左边大右边小不折下标 2 的 2左边 4 大于 2右边 6 大于 2它同时小于两边是谷折点数 1下标 3 的 6左边 2 小于 6右边 3 小于 6它同时大于两边是峰折点数 2下标 4 的 3左边 6 大于 3右边 1 小于 3左边大右边小不折下标 5 的 1左边 3 大于 1右边 2 大于 1它同时小于两边是谷折点数 3。最终输出就是 3。这个例子能帮我们把“山峰”和“山谷”的直觉落成明确的判断条件。1.3 边界位置到底算不算这个问题很基础但特别容易让人犹豫第一个数和最后一个数要不要判断答案是不要。因为在“折点”的定义里你需要看到该位置左边一个和右边一个数首尾元素缺了一侧就无法判断“同时大于两侧”或“同时小于两侧”。所以参考答案给的统计区间永远是中间位置也就是从下标 1 循环到 n-2。相等值同样不算。考虑序列 [1, 2, 2, 1]中间有两个 2。下标 1 的 2右侧还是 2不满足“严格大于两边”因为 2 2 不成立它也不满足“严格小于两边”。下标 2 的 2左边也是 2同样不满足严格条件。所以这个序列一个折点都没有。这句话我得强调两遍用 和 就错了题目写“大于/小于”就是严格的“大于/小于”。这为后面代码实现埋下伏笔如果你想在几秒内敲出满分代码必须先把“严格”这两个字写进判断里。2. 核心思路把判断翻译成一行条件2.1 从“方向改变”理解折点如果从趋势变化角度看折点出现的位置就是序列从上升变下降或从下降变上升的那个中间点。上升变下降中间那个数比两边都高也就是峰下降变上升中间那个数比两边都低也就是谷。这个观察能让你写代码时更有底气你不是在机械地比大小而是在检测走势的拐弯。所以判断条件完全可以写成if ((a[i] a[i-1] a[i] a[i1]) || (a[i] a[i-1] a[i] a[i1])) { cnt; }左边一半是峰右边一半是谷。两条分支用或连接因为峰和谷都计数。2.2 循环范围和下标细节要让这个判断有效i 必须既访问到 i-1 又访问到 i1。数组是从 0 开始编号的所以 i 最小是 1最大是 n-2。循环写成for (int i 1; i n-1; i)是最标准的写法。如果你写成i n程序不会马上报错但访问 a[n] 或 a[i1] 时就越界了。有时候在线评测环境里越界不一定崩溃但结果会莫名其妙地不对或者在某些测试点上崩溃。边界情况是 n 小于 3。只有一个数或两个数的时候没有哪个位置能同时看到左右两侧所以折点数一定是 0。数组版代码可以不用额外判断因为循环条件i n-1会自动让循环不执行但流式版本需要单独处理否则读数据时会出问题。这个细节放到后面专门说。2.3 复杂度为什么能做到 O(n)我的习惯是先估算复杂度再动手。这个题只需要把序列从头到尾过一遍每个位置做常数次比较所以时间复杂度是 O(n)。如果用数组存下所有数空间复杂度是 O(n)。如果按流式方式读取只用三个变量滚动更新空间复杂度能压到 O(1)。对第一题来说O(n) 已经是最优复杂度因为至少要读一遍全部输入才能知道折点数量。考试时看到 n 是 1000 级别任何写法都能过但如果以后遇到数据流或超大规模序列O(1) 空间的滚动写法就更有价值。3. 三种语言实现与代码细节3.1 C 数组版最直观的版本是读一个数组然后做一次循环。示例#include iostream using namespace std; int main() { int n; cin n; int a[n 5]; for (int i 0; i n; i) { cin a[i]; } int cnt 0; for (int i 1; i n - 1; i) { if ((a[i] a[i-1] a[i] a[i1]) || (a[i] a[i-1] a[i] a[i1])) { cnt; } } cout cnt endl; return 0; }这里把数组长度写成 n5不是因为我需要那么多空间而是为了“防一手”。很多初学者把数组开成正好 n一旦某个边界条件写错就可能访问到数组外面。多开几个单位只浪费几个 int能换来更稳定的评测体验。3.2 Java 版Java 的写法思路完全一样只需要注意 Scanner 读入和数组构建。示例import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n 5]; for (int i 0; i n; i) { a[i] sc.nextInt(); } int cnt 0; for (int i 1; i n - 1; i) { if ((a[i] a[i-1] a[i] a[i1]) || (a[i] a[i-1] a[i] a[i1])) { cnt; } } System.out.println(cnt); sc.close(); } }在 Java 中new int[n5]也顺手把越界风险降低了。Scanner 对于 1000 级别的输入完全够用不需要上 BufferedReader。3.3 Python 版Python 写起来最像伪代码。示例n int(input()) a list(map(int, input().split())) cnt 0 for i in range(1, n - 1): if (a[i] a[i-1] and a[i] a[i1]) or (a[i] a[i-1] and a[i] a[i1]): cnt 1 print(cnt)唯一需要注意的是range(1, n-1)在 Python 里是左闭右开它正好覆盖 1 到 n-2。很多初学者在这里写成range(1, n)导致最后一个中间点下标 n-1 访问 a[n] 越界。这行边界和 C 的i n-1是一样的只是表达方式不同。3.4 空间优化不存数组也能算如果我想在面试里让代码显得更漂亮会把数组版改成滚动变量版。思路是这样先读前两个数然后每读一个新数就看看“中间那个数”是不是折点。因为判断某个数是不是折点只需要它自己、它左边一个、它右边一个这三个数据不需要保存整个序列。#include iostream using namespace std; int main() { int n; cin n; if (n 3) { for (int i 0; i n; i) { int tmp; cin tmp; } cout 0 endl; return 0; } int first, second, third; cin first second; int cnt 0; for (int i 2; i n; i) { cin third; if ((second first second third) || (second first second third)) { cnt; } first second; second third; } cout cnt endl; return 0; }这里first、second、third就像传送带上的三个货物。判断完一个点之后整个窗口往右滑一格。n 3的处理逻辑在数组版里可以省略但流式版必须单独处理因为如果 n1 或 n2你没有足够的数去填first和second。如果这个分支没写好程序可能读不到正确的输入数据。3.5 代码里的“隐藏细节”有几个细节会直接影响分数但题目描述里不会画重点。第一输出只有一行一个整数不要额外打印“答案是”之类的提示语在线评测只看标准输出。第二输入数字之间可能有多个空格或者换行用 cin、Scanner、input().split() 都能自动消化不用担心。第三如果数组值可能很大用 int 一般没问题但保险起见可以用 long long。这道题的数字范围不会大到溢出 int养成看数据范围的习惯总没错。4. 做题时最容易错的四个地方4.1 把“严格大于/小于”写成允许相等这是我见过最普遍的失误。有人会把判断写成a[i] a[i-1] a[i] a[i1]认为“和旁边一样高也算峰”。实际上题目要的是“严格大”或“严格小”相等时不算。序列 [1, 2, 2, 1] 如果按 判断下标 1 和下标 2 都会被认为是峰最终输出 2而正确答案是 0。这种错误在自测普通递增递减序列时往往测不出来偏偏评测数据里可能藏着带相等值的用例一下就丢分。4.2 把首尾两个元素也算进去有的同学看完题觉得“第一个数只有一个邻居如果它比邻居大不也是折点吗”想法可以理解但题目定义不接受。折点必须“同时”和左右两侧比较缺哪一侧都不行。如果手写特判把 a[0] 或 a[n-1] 加进去几个测试点可能错一半。解决办法是老老实实把循环范围写成从 1 到 n-2不额外开小灶。4.3 循环边界写错C 里常见的错误是for (int i 1; i n-1; i)最后一次 i n-1 时访问 a[i1] 就越界。Java 和 Python 有类似问题。另一种是写for (int i 0; i n; i)把首尾也遍历了。这类错误定位起来并不难自己本地跑一下样例就能发现但如果在评测时才暴露很容易让人怀疑算法思路实际上只是下标差一点。4.4 不处理很小的 n虽然正式评测数据里 n 通常不小于 3但数组版代码在 n1 或 n2 时也能正确输出 0因为循环不进入。流式版则不同必须先处理n 3的情况否则first和second都没读全后面逻辑全乱。我建议不管哪种写法都在脑子里过一遍边界n1、n2、n3。这三个边界能帮你抓住一大半低级 bug。4.5 把简单问题想复杂还有一个心态问题。第一题往往很简单但有些人会怀疑“不可能这么简单吧”于是强行往单调栈、动态规划、滑动窗口上靠。说实话这类题就是让你拿分练手的题目名字都叫“折点计数”核心就是一次遍历加相邻三数比较。你非要引入额外数据结构反而容易写错。做题先读题再确认数据范围最后写最朴素的解法这是我一直以来的顺序。5. 差分视角换个方法理解折点5.1 连续差值符号折点其实也可以用差分来理解。把原序列变成相邻两数的差diff[i] a[i] - a[i-1]就能看到每一步是上升还是下降。如果 diff[i] 是正数说明 a[i] 比 a[i-1] 高如果是负数说明 a[i] 比 a[i-1] 低。当 diff 的符号从正变成负说明序列先上升后下降中间就是峰从负变成正说明先下降后上升中间就是谷。这样一来求折点就等价于数相邻差值符号的变化次数。5.2 为什么差分方法遇到相等要小心差分思路好理解但实现时有个大坑如果序列里出现相邻相等diff 会变成 0。比如 [1, 2, 2, 1]diff 是 1、0、-1。符号从正到负之间隔着一个 0如果你硬要数“符号变化”就得先规定 0 算什么这就很容易出错。有人会把 0 当成正有人会当成负还有人可能直接把 0 跳过导致最终计数对不上原始定义。所以我的建议是原理上理解差分没问题考试时还是用最直接的相邻比较法更稳。除非你能保证输入数据里没有连续相等值否则差分法会带来额外麻烦。5.3 从折点计数到趋势分段别小看这题背后的思想。一旦有了折点整条序列就可以按“上升段”和“下降段”切开。折点就是趋势切换点很多真实业务场景都会用到类似逻辑股价有波动转折传感器读数有异常拐点甚至用户行为曲线也要找趋势变化。通过折点把连续数据分段再做局部拟合或异常检测是一套很常见的数据处理流程。从这个角度看第一题不是孤立的偏题它把一个很基础的“序列预处理”动作变成了可评测的算法题。6. 实测、复盘与一点心得6.1 自测用例设计我在本地验证时喜欢准备一组覆盖各种情况的用例n序列期望折点数为什么75 4 2 6 3 1 23两个谷一个峰51 2 3 2 11只有 3 是峰31 2 11中间是峰31 1 10相等不算120边界63 2 2 3 1 01相等导致只有一个折点每跑完一组我会把中间每一个位置的判断结果都写出来而不是只看最终输出。这样一旦结果不对能立刻知道是哪个位置误判。调试时输出这些信息正式提交前再删掉效率很高。6.2 评测拿满分的注意事项这道题要拿满分的核心不是玄学是彻底落实“严格比较”“首尾不算”“循环不越界”三条。提交前先把样例跑一遍再把上面表格里的边界用例跑一遍基本就稳了。语言选择方面C 可以把ios::sync_with_stdio(false)加上这不是必须的但可以避免输入输出缓冲带来的无谓性能问题。Python 直接读整行 split 即可不要用 input() 一个个数去拼。最重要的是题目要求输出几就输出几不要画蛇添足。6.3 做完之后还能做什么如果你认真做完这道题我建议马上给自己加两个小任务。第一把“峰”和“谷”分开统计看看各有多少个这只需要把||拆成两个 if。第二把题面改成“统计所有局部最大值的数量”并在数组版基础上写一版 O(1) 空间的滚动读取实现。这两个小练习能帮你把相邻比较、边界处理、空间优化一次练透以后遇到更复杂的极值相关题不会慌。做完这套自测和扩展之后我个人的体会是这类 100 分题真正考的不是天赋而是对题目文字的敬畏。很多人在简单题上丢分不是因为不会循环而是把“严格”看成“大于等于”把“两侧”看成“一侧也行”。我会在刷题时刻意训练一个动作先把手写用例和预期输出写在草稿纸上再敲代码。这个习惯帮我省下来的调试时间比我还背过的任何数据结构都要值钱。如果你正打算准备算法考试别因为这类题看起来简单就跳过把它当成一个训练读题、画用例、做边界验证的标本收益会比你想的更大。
