找出临界点之间的最小和最大距离 图解题解

这道题到底在问什么

输入

head = [3,1]

输出

[-1,-1](没有临界点)

输入

本节演示 head = [5,3,1,2,5,1,2]

输出

[1,3]

先想最直接的笨办法

记牢一句口诀:最小距离一定出现在相邻的两个临界点之间,最大距离一定是最后一个临界点减去第一个临界点。所以只要盯住 first 和 last 两个位置,一趟就能算完,不用把所有临界点两两枚举。（动画第 3 步）

最优解：一步一步想明白

1. 3记牢一句口诀:最小距离一定出现在相邻的两个临界点之间,最大距离一定是最后一个临界点减去第一个临界点。所以只要盯住 first 和 last 两个位置,一趟就能算完,不用把所有临界点两两枚举。
2. 4先看这条链表,7 个节点,从左到右依次是 5 3 1 2 5 1 2,最后跟着 null 表示到头。我们要找的临界点是严格的波峰或波谷。开扫之前准备两个记号,first 记第一个临界点的位置,last 记上一个临界点的位置,现在都还空着。接下来从第二个节点起,拿三元组一个一个判。
3. 5先立一条规矩。第一个节点 5 没有前邻居,第七个节点 2 没有后邻居,它们各缺一边,判不了严格波峰波谷,所以永远不可能是临界点。真正需要逐个检查的,是中间这五个既有前邻居又有后邻居的节点,也就是第二到第六个。看清楚这个范围,咱们就从第二个节点动手。
4. 6正式开算前,先用眼睛顺一遍这条链表的高低起伏:5 一路降到 3 再降到 1,这是往下走;到 1 是谷底,接着 2、5 往上爬,5 是个尖;再往后 1 又掉下去,最后 2 收尾。凭感觉,波谷像在那两个 1 上,波峰像在中间的 5 上。感觉归感觉,下面还是要一格一格拿三元组严格验证,别漏也别错。
5. 7三个指针停在第 2 个节点身上,中间是它自己,值为 3,左邻居是 5,右邻居是 1。判临界点只看一件事:中间这个 3 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
6. 8比一比:中间的 3。它比左边的 5 小或持平,却没有低过右边的 1,是在下坡途中,不是波峰也不是波谷。所以第 2 个节点不是临界点,first 和 last 都不动,minDist、maxDist 也不变。窗口继续往后滑一格。
7. 9三个指针停在第 3 个节点身上,中间是它自己,值为 1,左邻居是 3,右邻居是 2。判临界点只看一件事:中间这个 1 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
8. 10比一比:中间的 1 严格小于左边的 3,也严格小于右边的 2,陷在两边下面,这是一个波谷,也就是局部极小值点。第 3 个节点确认是临界点,标蓝记下。下一帧看它带来的距离更新。
9. 11这是我们碰到的第一个临界点,位置是第 3 个节点。手里还只有它一个,构不成一对,所以还算不出任何距离。把 first 和 last 都记成 3,minDist 先当作无穷大挂着,maxDist 先当零。等下一个临界点出现,才有得比。
10. 12三个指针停在第 4 个节点身上,中间是它自己,值为 2,左邻居是 1,右邻居是 5。判临界点只看一件事:中间这个 2 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
11. 13比一比:中间的 2。它比左边的 1 大或持平,却没有超过右边的 5,是在上坡途中,不是波峰也不是波谷。所以第 4 个节点不是临界点,first 和 last 都不动,minDist、maxDist 也不变。窗口继续往后滑一格。
12. 14三个指针停在第 5 个节点身上,中间是它自己,值为 5,左邻居是 2,右邻居是 1。判临界点只看一件事:中间这个 5 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
13. 15比一比:中间的 5 严格大于左边的 2,也严格大于右边的 1,两边都压过,这是一个波峰,也就是局部极大值点。第 5 个节点确认是临界点,把它标蓝记下来。接下来该更新距离了。
14. 16又找到一个临界点,位置第 5 个节点。先算相邻差:它减去上一个临界点位置 3,等于 2,minDist 第一次有值,记成相邻差 2。再算首尾差:它减去第一个临界点位置 3,等于 2,maxDist 在 0 和首尾差 2 里取大,变成 2。最后把 last 挪到 5,等着后面的临界点接着比。
15. 17三个指针停在第 6 个节点身上,中间是它自己,值为 1,左邻居是 5,右邻居是 2。判临界点只看一件事:中间这个 1 是不是同时严格大于两个邻居,或者同时严格小于两个邻居。先把三个数摆好,下一帧下结论。
16. 18比一比:中间的 1 严格小于左边的 5,也严格小于右边的 2,陷在两边下面,这是一个波谷,也就是局部极小值点。第 6 个节点确认是临界点,标蓝记下。下一帧看它带来的距离更新。
17. 19又找到一个临界点,位置第 6 个节点。先算相邻差:它减去上一个临界点位置 5,等于 1,minDist 在 2 和相邻差 1 里取小,变成 1。再算首尾差:它减去第一个临界点位置 3,等于 3,maxDist 在 2 和首尾差 3 里取大,变成 3。最后把 last 挪到 6,等着后面的临界点接着比。
18. 20窗口滑到第七个节点了,它是尾节点,后面就是 null,没有右邻居,判不了临界点。整条链表已经扫完,一趟就够。回头看,这次一共揪出三个临界点,分别在第 3、5、6 个节点上。
19. 21把三个临界点一起亮出来:第三个节点的 1 是波谷,第五个节点的 5 是波峰,第六个节点的 1 又是波谷。它们在链表上的位置分别是 3、5、6。现在手里有了这三个位置,最小距离和最大距离到底怎么来的,下面两帧给你说透。
20. 22先说最小距离。三个临界点位置排好是 3、5、6,它们本来就是从左到右递增的。要让两个位置之差最小,当然是挨得最近的一对,也就是相邻的两个。3 到 5 差 2,5 到 6 差 1,最小的是 5 到 6 这一对,差 1。所以扫描时只拿当前和上一个临界点比,就能锁住最小距离,根本不用把所有对两两枚举。
21. 23再说最大距离。位置是递增的,要让差最大,自然是最靠右的减最靠左的,也就是最后一个临界点减第一个临界点。这里是 6 减 3,等于 3。所以扫描时只要盯住第一个临界点位置 first 不动,拿每个新临界点减 first 去刷新最大值就行。这就是为什么代码里只留 first 和 last 两个变量。
22. 24把账再算一遍核对。三个临界点位置 3、5、6,相邻的两对是 3 到 5 差 2、5 到 6 差 1,这两个里最小的是 1,正好是 minDist。跨度最大的一对是首尾 3 和 6,差 3,正好是 maxDist。哪怕把 3 到 6 之外的所有配对都列出来,也超不过这两个极值。账对上了,可以收了。
23. 25收工。最小距离出在位置 5 和位置 6 这两个相邻临界点,差 1;最大距离出在位置 3 和位置 6 这两个首尾临界点,差 3。所以答案是 1 和 3,和题目示例二对上了。整条链表只走了一遍,期间只用了 first、last、minDist、maxDist 几个变量,又快又省。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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 = right
class 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 = next
class 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        vector<int> ans = {1 << 30, 0};
        int first = -1, last = -1;
        for (int i = 0; head->next->next; head = head->next, ++i) {
            int a = head->val, b = head->next->val, c = head->next->next->val;
            if (b < min(a, c) || b > max(a, c)) {
                if (last == -1) {
                    first = i;
                    last = i;
                } else {
                    ans[0] = min(ans[0], i - last);
                    last = i;
                    ans[1] = max(ans[1], last - first);
                }
            }
        }
        return first == last ? vector<int>{-1, -1} : ans;
    }
};

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        int[] ans = {1 << 30, 0};
        int first = -1, last = -1;
        for (int i = 0; head.next.next != null; head = head.next, ++i) {
            int a = head.val, b = head.next.val, c = head.next.next.val;
            if (b < Math.min(a, c) || b > Math.max(a, c)) {
                if (last == -1) {
                    first = i;
                    last = i;
                } else {
                    ans[0] = Math.min(ans[0], i - last);
                    last = i;
                    ans[1] = Math.max(ans[1], last - first);
                }
            }
        }
        return first == last ? new int[] {-1, -1} : ans;
    }
}

复杂度

面试官可能追问