每日一题《leetcode--2058. 找出临界点之间的最小和最大距离》

https://leetcode.cn/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/

 

 

---

这道题要求我们求出临界点的最大距离和最小距离。要想求最大和最小距离，首先我们得先求出每个临界点。

这是题目给出的临界点的定义：

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

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

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

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int max(int a , int b )
{
    return (a > b ? a : b);
}

int min(int a , int b)
{
    return (a < b ? a : b);
}

int* nodesBetweenCriticalPoints(struct ListNode* head, int* returnSize) {
    //创建返回数组
    int* ret = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;
    int minDist = -1, maxDist = -1;
    int pos = 0,last = -1,first = -1;
    struct ListNode* cur = head;

    if(cur->next->next)
    {
        //寻找临界值
        while(cur->next->next)
        {   
            //存储三个连续的结点的值
            int x = cur->val;
            int y = cur->next->val;
            int z = cur->next->next->val;

            //假定y是临界值
            if(y > max(x,z) || y < min(x,z) )
            {
                if(last != -1)
                {   
                    //用相邻临界点的距离更新最小值
                    minDist = (minDist == -1? pos - last : min(minDist , pos - last));

                    //用第一个临界点的距离更新最大值
                    maxDist = (maxDist == -1? pos - first : max(maxDist , pos - first));
                }

                if(first == -1)
                {
                    first = pos;
                }
                
                //更新上一个临界点
                last = pos;
            }

            cur = cur->next;
            ++pos;

            ret[0] = minDist;
            ret[1] = maxDist;
        }
    }
    else
    {
        ret[0] = -1;
        ret[1] =-1;
    }
    
    return ret;
}