链表中的临界点定义为一个局部极大值点或局部极小值点 。如果当前节点的值严格大于前一个节点和后一个节点那么这个节点就是一个局部极大值点。如果当前节点的值严格小于前一个节点和后一个节点那么这个节点就是一个局部极小值点。注意节点只有在同时存在前一个节点和后一个节点的情况下才能成为一个局部极大值点 / 极小值点。给你一个链表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, 10^5]内1 Node.val 10^5分析遍历链表途中需要记录三个值第一个临界点最后一个临界点和倒数第二个临界点这三个点在链表中的位置设为 a,b,c。倒数第二个临界点可以是第一个临界点。这样求任意两个不同临界点之间的最小距离即为 c-b 的最小值任意两个不同临界点之间的最大距离即为 c-a。/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int* nodesBetweenCriticalPoints(struct ListNode* head, int* returnSize) { int *ans(int*)malloc(sizeof(int)*2); ans[0]ans[1]-1,*returnSize2; int a,b,c,cnt1;abc-1; struct ListNode *phead,*qhead-next; while(q-next!NULL) { if((q-valp-valq-valq-next-val)||(q-valp-valq-valq-next-val)) { ccnt; if(a-1)acnt; else if(b-1)bcnt,ans[0]ans[1]c-a; else ans[1]c-a,ans[0]ans[0]c-b?ans[0]:c-b,bc; } pq,qq-next,cnt; } return ans; }
