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