题目描述
思路解析动画文字版
记牢一句口诀:最小距离一定出现在相邻的两个临界点之间,最大距离一定是最后一个临界点减去第一个临界点。所以只要盯住 first 和 last 两个位置,一趟就能算完,不用把所有临界点两两枚举。
总览 · 从第二个节点开始逐个判临界点：先看这条链表,7 个节点,从左到右依次是 5 3 1 2 5 1 2,最后跟着 null 表示到头。我们要找的临界点是严格的波峰或波谷。开扫之前准备两个记号,first 记第一个临界点的位置,last 记上一个临界点的位置,现在都还空着。接下来从第二个节点起,拿三元组一个一个判。
端点法则 · 首尾节点永远不是临界点：先立一条规矩。第一个节点 5 没有前邻居,第七个节点 2 没有后邻居,它们各缺一边,判不了严格波峰波谷,所以永远不可能是临界点。真正需要逐个检查的,是中间这五个既有前邻居又有后邻居的节点,也就是第二到第六个。看清楚这个范围,咱们就从第二个节点动手。
预览 · 先肉眼扫一眼整条链表的起伏：正式开算前,先用眼睛顺一遍这条链表的高低起伏:5 一路降到 3 再降到 1,这是往下走;到 1 是谷底,接着 2、5 往上爬,5 是个尖;再往后 1 又掉下去,最后 2 收尾。凭感觉,波谷像在那两个 1 上,波峰像在中间的 5 上。感觉归感觉,下面还是要一格一格拿三元组严格验证,别漏也别错。
定位 · 看第 2 个节点的三元组 5 3 1：三个指针停在第 2 个节点身上,中间是它自己,值为 3,左邻居是 5,右邻居是 1。判临界点只看一件事:中间这个 3 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
判定 · 第 2 个节点不是临界点：比一比:中间的 3。它比左边的 5 小或持平,却没有低过右边的 1,是在下坡途中,不是波峰也不是波谷。所以第 2 个节点不是临界点,first 和 last 都不动,minDist、maxDist 也不变。窗口继续往后滑一格。
定位 · 看第 3 个节点的三元组 3 1 2：三个指针停在第 3 个节点身上,中间是它自己,值为 1,左邻居是 3,右邻居是 2。判临界点只看一件事:中间这个 1 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
判定 · 第 3 个节点是局部极小值点：比一比:中间的 1 严格小于左边的 3,也严格小于右边的 2,陷在两边下面,这是一个波谷,也就是局部极小值点。第 3 个节点确认是临界点,标蓝记下。下一帧看它带来的距离更新。
记录 · 这是第一个临界点,位置 = 3：这是我们碰到的第一个临界点,位置是第 3 个节点。手里还只有它一个,构不成一对,所以还算不出任何距离。把 first 和 last 都记成 3,minDist 先当作无穷大挂着,maxDist 先当零。等下一个临界点出现,才有得比。
定位 · 看第 4 个节点的三元组 1 2 5：三个指针停在第 4 个节点身上,中间是它自己,值为 2,左邻居是 1,右邻居是 5。判临界点只看一件事:中间这个 2 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
判定 · 第 4 个节点不是临界点：比一比:中间的 2。它比左边的 1 大或持平,却没有超过右边的 5,是在上坡途中,不是波峰也不是波谷。所以第 4 个节点不是临界点,first 和 last 都不动,minDist、maxDist 也不变。窗口继续往后滑一格。
定位 · 看第 5 个节点的三元组 2 5 1：三个指针停在第 5 个节点身上,中间是它自己,值为 5,左邻居是 2,右邻居是 1。判临界点只看一件事:中间这个 5 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
判定 · 第 5 个节点是局部极大值点：比一比:中间的 5 严格大于左边的 2,也严格大于右边的 1,两边都压过,这是一个波峰,也就是局部极大值点。第 5 个节点确认是临界点,把它标蓝记下来。接下来该更新距离了。
更新距离 · 相邻差 2 → minDist 2 ｜ 首尾差 2 → maxDist 2：又找到一个临界点,位置第 5 个节点。先算相邻差:它减去上一个临界点位置 3,等于 2,minDist 第一次有值,记成相邻差 2。再算首尾差:它减去第一个临界点位置 3,等于 2,maxDist 在 0 和首尾差 2 里取大,变成 2。最后把 last 挪到 5,等着后面的临界点接着比。
定位 · 看第 6 个节点的三元组 5 1 2：三个指针停在第 6 个节点身上,中间是它自己,值为 1,左邻居是 5,右邻居是 2。判临界点只看一件事:中间这个 1 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
判定 · 第 6 个节点是局部极小值点：比一比:中间的 1 严格小于左边的 5,也严格小于右边的 2,陷在两边下面,这是一个波谷,也就是局部极小值点。第 6 个节点确认是临界点,标蓝记下。下一帧看它带来的距离更新。
更新距离 · 相邻差 1 → minDist 1 ｜ 首尾差 3 → maxDist 3：又找到一个临界点,位置第 6 个节点。先算相邻差:它减去上一个临界点位置 5,等于 1,minDist 在 2 和相邻差 1 里取小,变成 1。再算首尾差:它减去第一个临界点位置 3,等于 3,maxDist 在 2 和首尾差 3 里取大,变成 3。最后把 last 挪到 6,等着后面的临界点接着比。
收尾 · 走到第 7 个节点,它是尾节点,停：窗口滑到第七个节点了,它是尾节点,后面就是 null,没有右邻居,判不了临界点。整条链表已经扫完,一趟就够。回头看,这次一共揪出三个临界点,分别在第 3、5、6 个节点上。
汇总 · 三个临界点全部标蓝,位置 3,5,6：把三个临界点一起亮出来:第三个节点的 1 是波谷,第五个节点的 5 是波峰,第六个节点的 1 又是波谷。它们在链表上的位置分别是 3、5、6。现在手里有了这三个位置,最小距离和最大距离到底怎么来的,下面两帧给你说透。
道理一 · 最小距离一定在相邻两临界点之间：先说最小距离。三个临界点位置排好是 3、5、6,它们本来就是从左到右递增的。要让两个位置之差最小,当然是挨得最近的一对,也就是相邻的两个。3 到 5 差 2,5 到 6 差 1,最小的是 5 到 6 这一对,差 1。所以扫描时只拿当前和上一个临界点比,就能锁住最小距离,根本不用把所有对两两枚举。
道理二 · 最大距离一定是首尾两临界点之差：再说最大距离。位置是递增的,要让差最大,自然是最靠右的减最靠左的,也就是最后一个临界点减第一个临界点。这里是 6 减 3,等于 3。所以扫描时只要盯住第一个临界点位置 first 不动,拿每个新临界点减 first 去刷新最大值就行。这就是为什么代码里只留 first 和 last 两个变量。
对照 · 把三对距离摆出来验一遍：把账再算一遍核对。三个临界点位置 3、5、6,相邻的两对是 3 到 5 差 2、5 到 6 差 1,这两个里最小的是 1,正好是 minDist。跨度最大的一对是首尾 3 和 6,差 3,正好是 maxDist。哪怕把 3 到 6 之外的所有配对都列出来,也超不过这两个极值。账对上了,可以收了。
完成 · 答案 [1, 3]：收工。最小距离出在位置 5 和位置 6 这两个相邻临界点,差 1;最大距离出在位置 3 和位置 6 这两个首尾临界点,差 3。所以答案是 1 和 3,和题目示例二对上了。整条链表只走了一遍,期间只用了 first、last、minDist、maxDist 几个变量,又快又省。
边界看三种:节点太少没临界点、相等不算严格、只有两个临界点时最小最大相等。
面试重点:三元组滑窗一趟扫、最小看相邻最大看首尾、O(n) 时间 O(1) 空间、当心严格与端点。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]: ans = [inf, -inf] first = last = -1 i = 0 while head.next.next: a, b, c = head.val, head.next.val, head.next.next.val if a > b < c or a < b > c: if last == -1: first = last = i else: ans[0] = min(ans[0], i - last) last = i ans[1] = max(ans[1], last - first) i += 1 head = head.next return [-1, -1] if first == last else ans复杂度
- 时间：O(n)，n 是链表节点数。三元组窗口从头滑到尾只走一趟,每个节点做一次常数比较和常数次距离更新
- 空间：O(1)，只用了 first、last、minDist、maxDist 这几个整型变量,没有再开和链表长度成正比的结构,峰值占用是常数
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问为什么最小看相邻、最大看首尾?
追问复杂度和易错点?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
反转偶数长度组的节点
LeetCode 2074 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题