我只會寫糞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;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.45.91 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720176450.A.A25.html