leetcode链表之找出临界值之间的最小和最大距离

2058、找出临界值之间的最小和最大距离

题目：

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

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

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

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

给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1] 。

示例1：

输入：head = [3,1]
输出：[-1,-1]

示例2：

输入：head = [5,3,1,2,5,1,2]
输出：[1,3]

示例3：

输入：head = [1,3,2,2,3,2,2,2,7]
输出：[3,3]

示例4：

输入：head = [2,3,3,2]
输出：[-1,-1]

思路：

遍历链表可以找到局部极大值和局部极小值，最大距离就是首尾两个极值位置之差，最小距离就是取两个极值之间的最小距离.

class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        if not head or not head.next or not head.next.next: return [-1, -1]
        prev, cur = head, head.next
        pos = 2
        first, last = -1, -1
        minDis, maxDis = -1, -1
        while cur.next:
            # 判断极值点
            if (prev.val > cur.val and cur.next.val > cur.val) or (prev.val < cur.val and cur.next.val < cur.val):
                if last != -1:
                    # 最小距离，每次取这次极值位置和上次极值的差，取最小值
                    minDis = (pos - last) if minDis == -1 else min(minDis, pos - last)
                    maxDis = pos - first
                # first记录首个极值的位置，用来求最大距离
                if first == -1:
                    first = pos
                # last记录上个极值的位置
                last = pos
            prev = cur
            cur = cur.next
            pos += 1
        return [minDis, maxDis]