2058.
抓critical point
linked-list從頭跑到尾
換換換
原本懶得寫換換換 所以用recursive
想讓他自己抓抓抓 結果射出一個TLE
我好笨:p
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
vector<int> nodesBetweenCriticalPoints(ListNode* head) {
vector <int> f({-1, -1});
ListNode* pre = head;
ListNode* cur = head->next;
if(cur == nullptr) return f;
ListNode* nxt = cur->next;
if(nxt == nullptr) return f;
vector<int> crit;
//getCrit(crit, pre, cur, nxt, 1);
int minD = INT_MAX;
for(int i = 1; nxt != nullptr; i++){
if( (pre->val > cur->val and nxt->val > cur->val)\
or(pre->val < cur->val and nxt->val < cur->val)){
if(!crit.empty()) minD = min(minD, i - crit.back());
crit.push_back(i);
}
pre = cur; cur = nxt; nxt = nxt->next;
}
if(crit.size() < 2) return f;
// for(int i = 1; i < crit.size(); i++){
// minD = min(minD, crit[i] - crit[i-1]);
// }
return {minD, crit.back() - crit.front()};
}
// void getCrit(vector<int>& crit, ListNode* pre, ListNode* cur, ListNode* nxt, int idx ){
// if(nxt == nullptr) return;
// if((pre->val > cur->val and nxt->val > cur->val)\
// or(pre->val < cur->val and nxt->val < cur->val)){
// crit.push_back(idx);
// }
// getCrit(crit, cur, nxt, nxt->next, idx+1);
// }
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720189643.A.BE0.html