LeetCode 每日一题笔记

0. 前言

• 日期：2026.09.01
• 题目：2058. 找出临界点之间的最小和最大距离
• 难度：中等
• 标签：链表

1. 题目理解

问题描述 临界点定义：局部极大值点或者局部极小值点。 局部极大：当前节点严格大于前后两个节点； 局部极小：当前节点严格小于前后两个节点。 只有同时存在前驱、后继的节点才可以成为临界点。 给定链表头结点，返回数组[minDistance, maxDistance]。 minDistance：任意两个临界点之间最小距离； maxDistance：任意两个临界点之间最大距离； 临界点数量小于2，返回[-1,-1]。

示例

输入：head = [5,3,1,2,5,1,2] 临界点位置：3、5、6 最小距离：1，最大距离：3 输出：[1,3]

2. 解题思路

核心观察

1. 临界点必须有前驱后继，链表头和尾节点不可能是临界点；
2. 最大距离 = 最后一个临界点位置 − 第一个临界点位置；
3. 最小距离是相邻临界点位置差值的最小值；
4. 遍历一遍链表，记录所有临界点下标，遍历过程中即可更新最小距离，不需要全部存完再遍历；
5. 若临界点数目不足2直接返回[-1,-1]。

算法步骤

原版：

1. 遍历链表，维护前驱、当前、后继节点值，位置下标；
2. 判断是否为临界点，记录临界点位置；
3. 统计临界点数量，少于2返回[-1,-1]；
4. 最小距离取相邻临界点差值的最小值，最大距离取首尾临界点位置差。

优化：

1. 合并条件判断，简化逻辑；
2. 不使用ArrayList存储全部临界点，只用变量记录上一个临界点位置，节省空间；
3. 精简冗余变量，减少if分支。

3. 代码实现

package lc2000_lc2099.lc2058;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public int[] nodesBetweenCriticalPoints(ListNode head) {
        int count = 0;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int prev = -1;
        int cur = -1;
        int next = -1;
        int pos = 1;
        int prevPos = -1;
        int res1 = Integer.MAX_VALUE;
        int res2 = -1;
        List<Integer> cc = new ArrayList<Integer>();
        ListNode curPos = head;
        while (curPos.next != null) {
            prev = cur;
            cur = curPos.val;
            next = curPos.next.val;
            if (cur < prev && cur < next && prev != -1 && next != -1 || cur > prev && cur > next && prev != -1 && next != -1) {
                if (pos < min) {
                    min = pos;
                }
                if (pos > max) {
                    max = pos;
                }
                if (res1 > pos - prevPos && prevPos != -1) {
                    res1 = pos - prevPos;
                }

                prevPos = pos;
                count++;
            }
            pos++;
            curPos = curPos.next;
        }

        if (count < 2) {
            return new int[]{-1, -1};
        }
        res2 = max - min;
        int[] res = {res1, res2};
        return res;
    }
}

4. 代码优化说明

class Solution {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public int[] nodesBetweenCriticalPoints(ListNode head) {
        // 记录上一个临界点位置
        int lastCritical = -1;
        // 第一个临界点位置
        int firstCritical = -1;
        int minDist = Integer.MAX_VALUE;
        int pos = 2;
        ListNode pre = head;
        ListNode curr = head.next;

        while (curr != null && curr.next != null) {
            ListNode nxt = curr.next;
            // 判断是否为临界点，合并大小条件
            boolean isCritical = (curr.val > pre.val && curr.val > nxt.val)
                    || (curr.val < pre.val && curr.val < nxt.val);
            if (isCritical) {
                if (firstCritical == -1) {
                    firstCritical = pos;
                } else {
                    // 更新相邻临界点最小距离
                    minDist = Math.min(minDist, pos - lastCritical);
                }
                lastCritical = pos;
            }
            pre = curr;
            curr = nxt;
            pos++;
        }
        // 临界点不足两个
        if (firstCritical == -1 || lastCritical == firstCritical) {
            return new int[]{-1, -1};
        }
        int maxDist = lastCritical - firstCritical;
        return new int[]{minDist, maxDist};
    }
}

5. 复杂度分析

• 原版代码 时间复杂度：$O(n)$，一次遍历链表； 空间复杂度：$O(n)$，使用ArrayList存储临界点。

• 优化版本 时间复杂度：$O(n)$，仅一次遍历链表； 空间复杂度：$O(1)$，仅使用有限变量，无额外集合存储。

6. 总结

• 核心：最大距离等于首尾临界点位置差；最小距离是相邻临界点的位置差的最小值；
• 优化亮点：不保存全部临界点，仅记录第一个、上一个临界点，省去集合开销；合并判断条件，减少if分支；
• 关键点：链表头、尾节点不可能成为临界点，遍历条件要保证curr存在后继节点。