鏈表中的臨界點定義為一個局部極大值點或局部極小值點 。如果當(dāng)前節(jié)點的值嚴格大于前一個節(jié)點和后一個節(jié)點那么這個節(jié)點就是一個局部極大值點。如果當(dāng)前節(jié)點的值嚴格小于前一個節(jié)點和后一個節(jié)點那么這個節(jié)點就是一個局部極小值點。注意節(jié)點只有在同時存在前一個節(jié)點和后一個節(jié)點的情況下才能成為一個局部極大值點 / 極小值點。給你一個鏈表head返回一個長度為 2 的數(shù)組[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]第三個節(jié)點是一個局部極小值點因為 1 比 3 和 2 小。 - [5,3,1,2,5,1,2]第五個節(jié)點是一個局部極大值點因為 5 比 2 和 1 大。 - [5,3,1,2,5,1,2]第六個節(jié)點是一個局部極小值點因為 1 比 5 和 2 小。 第五個節(jié)點和第六個節(jié)點之間距離最小。minDistance 6 - 5 1 。 第三個節(jié)點和第六個節(jié)點之間距離最大。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]第二個節(jié)點是一個局部極大值點因為 3 比 1 和 2 大。 - [1,3,2,2,3,2,2,2,7]第五個節(jié)點是一個局部極大值點因為 3 比 2 和 2 大。 最小和最大距離都存在于第二個節(jié)點和第五個節(jié)點之間。 因此minDistance 和 maxDistance 是 5 - 2 3 。 注意最后一個節(jié)點不算一個局部極大值點因為它之后就沒有節(jié)點了。示例 4輸入head [2,3,3,2]輸出[-1,-1]解釋鏈表 [2,3,3,2] 中不存在臨界點。提示鏈表中節(jié)點的數(shù)量在范圍[2, 10^5]內(nèi)1 Node.val 10^5分析遍歷鏈表途中需要記錄三個值第一個臨界點最后一個臨界點和倒數(shù)第二個臨界點這三個點在鏈表中的位置設(shè)為 a,b,c。倒數(shù)第二個臨界點可以是第一個臨界點。這樣求任意兩個不同臨界點之間的最小距離即為 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; }