【Leetcode Daily】2058找出临界点之间的最小和最大距离

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个长度至少为二的链表，其中可能存在局部的极大点或者极小点，返回极值点之间的最小距离和最大距离

思路分享

• 用 first 和 last 记录已经遍历到的最早和最晚的极值点，那么最大距离就是这两个之差，但是最小距离需要实时计算，每次可以拿新的极值点与 last 做差更新。

  https://leetcode.cn/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/solutions/1075991/go-mo-ni-bian-li-lian-biao-bian-li-lin-j-rx9s/

代码解答（强烈建议自行解答后再看）

• 参考题解

# 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, last = 0, 0
        a, b, c = head, head.next, head.next.next
        index = 1
        minDist = inf
        while c:
            if a.val < b.val > c.val or a.val > b.val < c.val:
                if first == 0:
                    first = index
                if last > 0 and index-last < minDist:
                    minDist = index-last
                last = index
            a, b, c = b, c, c.next
            index += 1
        return [minDist, last-first] if first != last else [-1, -1]