我只会写粪code了
2058. Find the Minimum and Maximum Number of Nodes Between Critical Points
critical point是指local maxima 或是 local minima
一个node是local maxima那他的value会大于前一个跟下一个node值
一个node是local minima那他的value会小于前一个跟下一个node值
如果node有previos/next node才有可能是local maxima/minima
给一个linked list
请回传任意两个critical point间距离的最大和最小值
如果critical point数量没有超过2个则回传[-1,-1]
思路:
原本想说把所有critcal point都找出来记录在一个array里
不过这样太麻烦了
先找出第一个critical point，并记录其位置
接着开始找接下来的critical point，要记录前一个critical point的位置
每次都去比较两个critical point的距离差是不是比较小
这样就可以找到最短的距离差
最大的距离差则是最后一个和第一个得差值
C code :
/**
* 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 cnt=1,*res=(int*)malloc(2*sizeof(int)),first=0,last=0;
res[0]=-1;
res[1]=-1;
(*returnSize)=2;
struct ListNode* prev=head;
head=head->next;
while(1){
if (head->next==NULL){
return res;
}
if ((prev->val < head->val && head->next->val < head->val) || (prev->
val > head->val && head->next->val > head->val)){
first=cnt++;
prev=head;
head=head->next;
break;
}
prev=head;
head=head->next;
cnt++;
}
int prevnum=first,mindist=100001;
while(1){
if (head->next==NULL){
if (mindist==100001){
return res;
}
res[0]=mindist;
res[1]=last-first;
return res;
}
if ((prev->val < head->val && head->next->val < head->val) || (prev->
val > head->val && head->next->val > head->val)){
last=cnt;
mindist = mindist < (cnt-prevnum) ? mindist : (cnt-prevnum);
prevnum=cnt;
}
cnt++;
prev=head;
head=head->next;
}
return res;
}