golang 解法, 执行用时: 144 ms, 内存消耗: 11.8 MB, 提交时间: 2022-12-08 11:53:26

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func nodesBetweenCriticalPoints(head *ListNode) []int {
	a, b, c := head, head.Next, head.Next.Next
	first, last, minDis := 0, 0, math.MaxInt32
	for i, prev := 1, 0; c != nil; i++ { // 遍历链表，寻找临界点
		if a.Val < b.Val && b.Val > c.Val || a.Val > b.Val && b.Val < c.Val {
			if first == 0 {
				first = i // 首个临界点位置
			}
			last = i // 最末临界点位置
			if prev > 0 && i-prev < minDis {
				minDis = i - prev // 更新相邻临界点位置之差的最小值
			}
			prev = i
		}
		a, b, c = b, c, c.Next
	}
	if first == last { // 临界点少于两个
		return []int{-1, -1}
	}
	return []int{minDis, last - first}
}

python3 解法, 执行用时: 880 ms, 内存消耗: 55.6 MB, 提交时间: 2022-12-08 11:53:03

# 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]:
        nums = []
        p = head
        while p:
            nums.append(p.val)
            p = p.next
        
        a = []
        n = len(nums)
        for i in range(1, n - 1):
            if nums[i - 1] > nums[i] < nums[i + 1]:
                a.append(i)
            elif nums[i - 1] < nums[i] > nums[i + 1]:
                a.append(i)
        
        if len(a) < 2:
            return [-1, -1]
        
        max_ = a[-1] - a[0]
        min_ = float('inf')
        for i in range(1, len(a)):
            min_ = min(min_, a[i] - a[i - 1])
        return [min_, max_]

python3 解法, 执行用时: 1012 ms, 内存消耗: 55.5 MB, 提交时间: 2022-12-08 11:52:24

# 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]:
        minDist = maxDist = -1
        first = last = -1
        pos = 0

        cur = head
        while cur.next.next:
            # 获取连续的三个节点的值
            x, y, z = cur.val, cur.next.val, cur.next.next.val
            # 如果 y 是临界点
            if y > max(x, z) or y < min(x, z):
                if last != -1:
                    # 用相邻临界点的距离更新最小值
                    minDist = (pos - last if minDist == -1 else min(minDist, pos - last))
                    # 用到第一个临界点的距离更新最大值
                    maxDist = max(maxDist, pos - first)
                if first == -1:
                    first = pos
                # 更新上一个临界点
                last = pos
            cur = cur.next
            pos += 1
        
        return [minDist, maxDist]