2058.找出临界点之间的最小和最大距离：遍历+遇到极值则更新(这种题谁空间复杂度不是O(1)啊)

【LetMeFly】2058.找出临界点之间的最小和最大距离：遍历+遇到极值则更新(这种题谁空间复杂度不是O(1)啊)

力扣题目链接：https://leetcode.cn/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/

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

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

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

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

给你一个链表 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 。
注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。

示例 4：

输入：head = [2,3,3,2]
输出：[-1,-1]
解释：链表 [2,3,3,2] 中不存在临界点。

 

提示：

• 链表中节点的数量在范围 [2, 105] 内
• 1 <= Node.val <= 105

解题方法：遍历

其实这道题遍历极值点并不难：

使用两个变量记录前两个节点的值，如果第二个节点相比第一个节点和当前节点都大/都小，则第二个节点即为极值点。

在此基础上维护极值点之间的最大最小间隔就可以了：

使用几个变量：上一个极值点下标、第一个极值点下标、最短距离、最大距离，初始值都是$-1$。

一旦遇到极值点，则看是否为第一个极值点（值为$-1$则是），若是第一个极值点则更新：上一个极值点下标、第一个极值点下标；否则则更新：最大距离（当前极值点下标 - 第一个极值点下标）、最小距离（min(上次最小距离, 当前极值点下标 - 上一个极值点下标)）、上一个极值点下标（更新为当前下标）

最后直接返回{最短距离、最大距离}就好。

• 时间复杂度$O(len(list))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-09-01 13:10:00
 */
class Solution {
private:
    int lastIdx = -1, firstIdx = -1;
    int mDis = -1;
    int MDis = -1;

    void updateDis(int idx) {
        // cout << idx << endl;
        if (lastIdx == -1) {
            firstIdx = lastIdx = idx;
            return;
        }
        int dis = idx - lastIdx;
        if (mDis == -1) {
            mDis = MDis = dis;
        } else {
            mDis = min(mDis, dis);
            MDis = idx - firstIdx;
        }
        lastIdx = idx;  // 看来思路还是不能断啊
    }
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        int firstVal = head->val;
        int secondVal = head->next->val;
        int idx = 0;
        for (head = head->next->next; head; head = head->next, idx++) {
            int nowVal = head->val;
            if (secondVal < firstVal && secondVal < nowVal || secondVal > firstVal && secondVal > nowVal) {
                updateDis(idx);
            }
            firstVal = secondVal;
            secondVal = nowVal;
        }
        return {mDis, MDis};
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源