LeetCode 题解工作台
找出临界点之间的最小和最大距离
链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。 如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个 局部极大值点 。 如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个 局部极小值点 。 注意：节点只有在同时存在前一个节点和后一个节点的情…
1
题型
5
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
根据题目描述，我们需要找出链表的第一个临界点和最后一个临界点位置 和 ，这样可以计算出最大距离 $\textit{maxDistance} = \textit{last} - \textit{first}$。对于最小距离 ，我们需要遍历链表，计算相邻两个临界点之间的距离，取最小值即可。 时间复杂度 ，其中 是链表的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。
如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个 局部极大值点 。
如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个 局部极小值点 。
注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。
给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1] 。
示例 1：
输入：head = [3,1] 输出：[-1,-1] 解释：链表 [3,1] 中不存在临界点。
示例 2：
输入：head = [5,3,1,2,5,1,2] 输出：[1,3] 解释：存在三个临界点： - [5,3,1,2,5,1,2]：第三个节点是一个局部极小值点，因为 1 比 3 和 2 小。 - [5,3,1,2,5,1,2]：第五个节点是一个局部极大值点，因为 5 比 2 和 1 大。 - [5,3,1,2,5,1,2]：第六个节点是一个局部极小值点，因为 1 比 5 和 2 小。 第五个节点和第六个节点之间距离最小。minDistance = 6 - 5 = 1 。 第三个节点和第六个节点之间距离最大。maxDistance = 6 - 3 = 3 。
示例 3：
输入：head = [1,3,2,2,3,2,2,2,7] 输出：[3,3] 解释：存在两个临界点： - [1,3,2,2,3,2,2,2,7]：第二个节点是一个局部极大值点，因为 3 比 1 和 2 大。 - [1,3,2,2,3,2,2,2,7]：第五个节点是一个局部极大值点，因为 3 比 2 和 2 大。 最小和最大距离都存在于第二个节点和第五个节点之间。 因此，minDistance 和 maxDistance 是 5 - 2 = 3 。 注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。
示例 4：
输入：head = [2,3,3,2] 输出：[-1,-1] 解释：链表 [2,3,3,2] 中不存在临界点。
提示：
- 链表中节点的数量在范围
[2, 105]内 1 <= Node.val <= 105
解题思路
方法一：直接遍历
根据题目描述，我们需要找出链表的第一个临界点和最后一个临界点位置 和 ，这样可以计算出最大距离 。对于最小距离 ，我们需要遍历链表，计算相邻两个临界点之间的距离，取最小值即可。
时间复杂度 ，其中 是链表的长度。空间复杂度 。
# 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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
The candidate should efficiently traverse the linked list and handle edge cases with minimal overhead.
- question_mark
Look for the ability to optimize the identification of local minima and maxima in a single pass.
- question_mark
The candidate must consider and handle edge cases where there are fewer than two critical points.
常见陷阱
外企场景- error
Overlooking edge cases where fewer than two critical points exist, leading to incorrect output.
- error
Failing to handle linked lists of small sizes (e.g., lists with only two nodes).
- error
Inefficient traversal or unnecessary extra space usage when iterating through the list.
进阶变体
外企场景- arrow_right_alt
Consider variations where the list may contain duplicate values that affect local maxima or minima.
- arrow_right_alt
Explore a version where the linked list is doubly linked, which might simplify some edge cases.
- arrow_right_alt
Modify the problem to find critical points based on other criteria, such as being greater than or less than neighboring nodes for multiple comparisons.