LeetCode2058. 找出临界点之间的最小和最大距离

本题，有一定难度，但不大(我设了个全局变量，被坑了

题目：

本题要我们求出两个极值点最大距离以及最小距离，如果不存在则返回[-1,-1]

不难看出，最小距离只会在相邻两个极值点取得，最大值则是一头一尾，这也启发我们要设置变量，用来记录头尾极值点的位置，以及两个相邻极值点的距离

代码如下：

typedef struct ListNode ListNode;
int* nodesBetweenCriticalPoints(struct ListNode* head, int* returnSize)
{
    ListNode* p = head;  //p向前滑动
    ListNode* q = NULL; //p的前驱
    int r = 0;    //当前极值点的位置
    int l = 0;    //上一个极值点的位置
    int s = INT_MAX;  //第一个极值点的位置
    int min = INT_MAX;//两个极值点之间的最小距离
    int max = -1; //两个极值点之间的最大距离
    int i = 0; //记录当前位置

    //答案数组   PS:千万不要搞全局，会被主函数修改。。。我就被硬控了。。。
    int* a = (int*)malloc(sizeof(int) * 2);
    a[0] = -1; a[1] = -1;

    while (p->next != NULL) //去掉尾结点
    {
        i++;
        if (q != NULL) //去掉头结点
        {
            ListNode* t = p->next; //让t指向p的后驱
            if (((q->val < p->val) && (p->val > t->val)) || ((q->val > p->val) && (p->val < t->val)))//判断极值点
            {
                if (s > i) //记录第一个极值点位置
                    s = i;
                if (r > 0)
                    l = r; //记录上一个极值点位置                

                r = i;  //记录当前极值点位置
                if (l > 0 && r > 0)
                    min = (min > (r - l)) ? (r - l) : min; //维护最小距离
            }
        }
        q = p;  //向前移动
        p = p->next;
    }

    *returnSize = 2;
    if (s != INT_MAX && r != 0 && l != 0)
    {
        max = r - s;
        a[0] = min;
        a[1] = max;
    }

    return a;
}