2024-07-05
2058. Find the Minimum and Maximum Number of Nodes Between Critical Points
A critical point in a linked list is defined as either a local maxima or a
local minima.
A node is a local maxima if the current node has a value strictly greater
than the previous node and the next node.
A node is a local minima if the current node has a value strictly smaller
than the previous node and the next node.
Note that a node can only be a local maxima/minima if there exists both a
previous node and a next node.
Given a linked list head, return an array of length 2 containing
[minDistance, maxDistance] where minDistance is the minimum distance between
any two distinct critical points and maxDistance is the maximum distance
between any two distinct critical points. If there are fewer than two
critical points, return [-1, -1].
因为是 LL 好像不能干嘛
只能乖乖走
程式会分两阶段
第一个部分先纪录符合条件的 node index
第二个部分算所有 index 之间的 min distance
max dist 直接是 index 最后减最前
我应该是少做 early return
还有多做 function 去判断 critical point
时间大概是 100% 的两倍
/**
* 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> ans(2, -1);
vector<int> idx;
int i = 1;
while (head->next && head->next->next) {
if (isCritical(head)) {
idx.push_back(i);
}
head = head->next;
i++;
}
if (idx.size() >= 2) {
ans[1] = idx.back() - idx.front();
ans[0] = idx[1] - idx[0];
for (int i = 2; i < idx.size(); i++) {
if (idx[i] - idx[i-1] < ans[0]) {
ans[0] = idx[i] - idx[i-1];
}
}
}
return ans;
}
private:
bool isCritical(ListNode* node) {
if (node->val < node->next->val && node->next->val >
node->next->next->val) {
return true;
}
if (node->val > node->next->val && node->next->val <
node->next->next->val) {
return true;
}
return false;
}
};