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

难度: Medium

链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点。

如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个 局部极大值点 。

如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个 局部极小值点 。

注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。

给你一个链表 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, 10⁵] 内
1 <= Node.val <= 10⁵

Submission

运行时间: 828 ms

内存: 56 MB

# 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]:
        first_i = None
        last_i = None
        p = head
        c = p.next
        n = c.next
        i = 0
        _min = 10 ** 5 + 1
        num = 0
        while n:
            if c.val < p.val and c.val < n.val or c.val > p.val and c.val > n.val:
                if first_i is None:
                    first_i = i
                if last_i is not None:
                    _min = min(_min, i - last_i)
                last_i = i
                num += 1
            p = p.next
            c = c.next
            n = n.next
            i += 1
        if num < 2:
            return [-1, -1]
        return [_min, last_i - first_i]

Explain

此题解的核心思路是遍历链表，同时检查每个节点是否是局部极大值点或局部极小值点。为此，代码使用三个指针p, c, n分别代表前一个节点、当前节点和下一个节点。遍历过程中，通过比较c节点的值与p和n的值来确定c是否为一个临界点。如果是，我们记录下该临界点的位置。通过维持两个变量first_i和last_i来记录遇到的第一个和最后一个临界点的位置，同时记录两个连续临界点之间的最小距离。最后，如果总临界点数量少于2，则返回[-1, -1]；否则返回记录的最小距离和第一个临界点与最后一个临界点之间的距离。

时间复杂度: O(n)

空间复杂度: O(1)

# 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]:
        first_i = None  # 用来记录第一个临界点的位置
        last_i = None   # 用来记录上一个临界点的位置
        p = head        # 初始化前一个节点
        c = p.next      # 初始化当前节点
        n = c.next      # 初始化下一个节点
        i = 0           # 当前节点的索引
        _min = 10 ** 5 + 1  # 初始化最小距离
        num = 0        # 临界点计数器
        while n:       # 遍历直至链表结束
            if c.val < p.val and c.val < n.val or c.val > p.val and c.val > n.val:  # 检查是否为临界点
                if first_i is None:  # 如果是第一个临界点
                    first_i = i
                if last_i is not None:  # 计算与上一个临界点的距离并更新最小距离
                    _min = min(_min, i - last_i)
                last_i = i  # 更新上一个临界点位置
                num += 1    # 临界点数量增加
            p = p.next      # 移动指针
            c = c.next
            n = n.next
            i += 1
        if num < 2:        # 如果临界点不足两个，返回[-1, -1]
            return [-1, -1]
        return [_min, last_i - first_i]  # 返回最小和最大距离

Explore

在此算法中，对于链表的头部和尾部节点，并没有进行临界点的判断。因为头部节点没有前驱节点，而尾部节点没有后继节点，所以无法使用给定的判断条件（即c节点是否同时大于或小于它的前驱节点p和后继节点n）来确定它们是否为临界点。因此，算法的临界点检查从链表的第二个节点开始，并在倒数第二个节点结束，确保每个被检查的节点都有前驱和后继。

在代码中，`first_i`变量用于记录遇到的第一个临界点的位置，而`last_i`变量用于记录最近一次遇到的临界点的位置。这两个变量的使用使得算法能够计算最小和最大距离。具体地，每次发现一个新的临界点时，使用`last_i`记录其位置，并计算与上一个临界点的距离，更新最小距离（如果当前距离小于已记录的最小距离）。`first_i`和最后一个`last_i`之间的差值给出了第一个和最后一个临界点之间的最大距离。

算法通过遍历链表，一直到倒数第二个节点，来检查每个节点是否为临界点。通过维护指针p（前一个节点），c（当前节点），和n（下一个节点），算法可以有效判断当前节点c是否满足临界点条件。一旦遍历完成，所有可能的临界点都被考虑过。使用`first_i`记录第一个临界点，以及更新`last_i`记录最后一个临界点，并在发现新临界点时更新最小距离。最终，通过比较`first_i`和最后一个`last_i`的差值，计算出最大距离。这样确保了所有临界点被找到并且正确计算了最小和最大距离。

在本题解中，指针n代表下一个节点，它会随着每次循环迭代向前移动。算法的循环条件是`n`不为空，这意味着当`n`指向链表的最后一个节点的下一个位置（即null）时，循环将停止。这样的循环条件确保了在最后一个节点之前的节点可以被检查是否为临界点，因为最后一个节点没有后继节点，不能根据给定条件判断其是否为临界点。因此，代码在n为null时自然结束循环，不进行额外操作。