Leetcode每日一题 —— 2058. 找出临界点之间的最小和最大距离

魔法师 2026-08-31 09:16 1

思路

模拟即可。

代码



class Solution {

    public int[] nodesBetweenCriticalPoints(ListNode head) {

        if (head.next == null || head.next.next == null) {

            return new int[]{ -1, -1 };

        }

        int mnDist = Integer.MAX_VALUE;

        int mxDist = 0;

        int idx = 0;

        int last = head.val;

        int first = -1;

        int lastIdx = -1;

        ListNode cur = head.next;

        while (cur.next != null) {

            if ((last > cur.val && cur.next.val > cur.val) || (last < cur.val && cur.next.val < cur.val)) {

                if (first == -1) {

                    first = idx;

                } else {

                    mnDist = Math.min(mnDist, idx - lastIdx);

                    mxDist = idx - first;

                }

                lastIdx = idx;

            }

            idx++;

            last = cur.val;

            cur = cur.next;

        }

        if (mnDist == Integer.MAX_VALUE) {

            return new int[]{ -1, -1 };

        }

        return new int[]{ mnDist, mxDist };

    }

}

最新回复 (2)

SomeBottle 08-31 09:16

1楼

简单链表题。

class Solution {

public:

    vector<int> nodesBetweenCriticalPoints(ListNode* head) {

        int prev=-1; // 记录上一个临界点的位置

        int first=-1; // 记录首个临界点位置

        int cnt=1; // 递增编号

        vector<int> res{100001,-1};

        ListNode* prevNode=nullptr;

        while(head!=nullptr){

            if(prevNode!=nullptr&&head->next!=nullptr&&(prevNode->val<head->val&&head->val>head->next->val||prevNode->val>head->val&&head->val<head->next->val)){

                if(first==-1){

                    first=cnt;

                }else{

                    res[1]=max(res[1],cnt-first);

                }

                if(prev!=-1){

                    res[0]=min(res[0],cnt-prev);

                }

                prev=cnt;

            }

            cnt++;

            prevNode=head;

            head=head->next;

        }

        if(res[0]==100001){

            res[0]=-1;

        }

        return res;

    }

};

Lvvvv 08-31 09:46

2楼

写了一坨

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode() : val(0), next(nullptr) {}

 *     ListNode(int x) : val(x), next(nullptr) {}

 *     ListNode(int x, ListNode *next) : val(x), next(next) {}

 * };

 */

class Solution {

public:

    vector<int> nodesBetweenCriticalPoints(ListNode* head) {

        vector<int> res = {-1,-1};

        if(head == nullptr || head->next == nullptr || head->next->next == nullptr) {

            return res;

        }

        int minid = -1,id = 1,lastid = -1;

        ListNode* p = head->next, *pre = head;

        while(p->next != nullptr) {

            if(static_cast<long long>((p->val - pre->val)) * (p->val - p->next->val) > 0) {

                if(minid != -1) {

                    minid = min(minid,id);

                } else {

                    minid = id;

                }

                if(res[0] == -1 && lastid != -1) {

                    res[0] = id - lastid;

                } else {

                    res[0] = min(res[0],id - lastid);

                }

                lastid = id;

            }

            id++;

            pre = p;

            p = p->next;

        }

        if(minid != lastid) {

            res[1] = lastid - minid;

        }

        return res;

    }

};

* 帖子来源Linux.do

附近帖子