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。

约束条件：

  • 链表中的节点数在范围 [2, 10^5] 内。
  • 1 <= Node.val <= 10^5

解题思路

思路分析

这道题目需要找到链表中所有的临界点（局部最大值或最小值），然后计算临界点之间的最小和最大距离。

核心思路：

  1. 一次遍历识别临界点：需要三个指针（prev、curr、next）来判断当前节点是否为临界点
  2. 最大距离优化：最大距离必定是第一个临界点到最后一个临界点的距离
  3. 最小距离计算：需要比较相邻临界点之间的距离

具体步骤：

  • 使用三个指针遍历链表，判断 curr 是否为临界点
  • 记录第一个临界点的位置（用于计算最大距离）
  • 记录上一个临界点的位置（用于计算最小距离）
  • 当找到新的临界点时，更新最小距离和最后一个临界点位置

判断临界点的条件：

  • 局部最大值：curr.val > prev.val && curr.val > next.val
  • 局部最小值：curr.val < prev.val && curr.val < next.val

这种方法只需要一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

边界情况处理：

  • 如果临界点少于 2 个，返回 [-1, -1]
  • 链表长度至少为 3 才可能有临界点

代码实现

class Solution {
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        if (!head || !head->next || !head->next->next) {
            return {-1, -1};
        }
        
        ListNode* prev = head;
        ListNode* curr = head->next;
        int position = 1;
        int firstCritical = -1, lastCritical = -1;
        int minDistance = INT_MAX;
        
        while (curr->next) {
            // 检查是否为临界点
            bool isMaxima = curr->val > prev->val && curr->val > curr->next->val;
            bool isMinima = curr->val < prev->val && curr->val < curr->next->val;
            
            if (isMaxima || isMinima) {
                if (firstCritical == -1) {
                    firstCritical = position;
                } else {
                    minDistance = min(minDistance, position - lastCritical);
                }
                lastCritical = position;
            }
            
            prev = curr;
            curr = curr->next;
            position++;
        }
        
        if (firstCritical == -1 || firstCritical == lastCritical) {
            return {-1, -1};
        }
        
        int maxDistance = lastCritical - firstCritical;
        return {minDistance, maxDistance};
    }
};

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 = head
        curr = head.next
        position = 1
        first_critical = -1
        last_critical = -1
        min_distance = float('inf')
        
        while curr.next:
            # 检查是否为临界点
            is_maxima = curr.val > prev.val and curr.val > curr.next.val
            is_minima = curr.val < prev.val and curr.val < curr.next.val
            
            if is_maxima or is_minima:
                if first_critical == -1:
                    first_critical = position
                else:
                    min_distance = min(min_distance, position - last_critical)
                last_critical = position
            
            prev = curr
            curr = curr.next
            position += 1
        
        if first_critical == -1 or first_critical == last_critical:
            return [-1, -1]
        
        max_distance = last_critical - first_critical
        return [min_distance, max_distance]

public class Solution {
    public int[] NodesBetweenCriticalPoints(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return new int[] {-1, -1};
        }
        
        ListNode prev = head;
        ListNode curr = head.next;
        int position = 1;
        int firstCritical = -1, lastCritical = -1;
        int minDistance = int.MaxValue;
        
        while (curr.next != null) {
            // 检查是否为临界点
            bool isMaxima = curr.val > prev.val && curr.val > curr.next.val;
            bool isMinima = curr.val < prev.val && curr.val < curr.next.val;
            
            if (isMaxima || isMinima) {
                if (firstCritical == -1) {
                    firstCritical = position;
                } else {
                    minDistance = Math.Min(minDistance, position - lastCritical);
                }
                lastCritical = position;
            }
            
            prev = curr;
            curr = curr.next;
            position++;
        }
        
        if (firstCritical == -1 || firstCritical == lastCritical) {
            return new int[] {-1, -1};
        }
        
        int maxDistance = lastCritical - firstCritical;
        return new int[] {minDistance, maxDistance};
    }
}

var nodesBetweenCriticalPoints = function(head) {
    let criticalPoints = [];
    let prev = head;
    let curr = head.next;
    let position = 1;
    
    while (curr && curr.next) {
        let next = curr.next;
        
        if ((curr.val > prev.val && curr.val > next.val) || 
            (curr.val < prev.val && curr.val < next.val)) {
            criticalPoints.push(position);
        }
        
        prev = curr;
        curr = next;
        position++;
    }
    
    if (criticalPoints.length < 2) {
        return [-1, -1];
    }
    
    let minDistance = Infinity;
    for (let i = 1; i < criticalPoints.length; i++) {
        minDistance = Math.min(minDistance, criticalPoints[i] - criticalPoints[i-1]);
    }
    
    let maxDistance = criticalPoints[criticalPoints.length - 1] - criticalPoints[0];
    
    return [minDistance, maxDistance];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要遍历整个链表一次，其中 n 是链表的长度
空间复杂度O(1)只使用了常数个变量来存储临界点位置和距离信息