网站建设尾款如何做会计分录,com域名续费多少钱,佛山网站专业制作,深圳发布广告的平台有哪些2058. 找出临界点之间的最小和最大距离
链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。
如果当前节点的值 严格大于 前一个节点和后一个节点#xff0c;那么这个节点就是一个 局部极大值点 。
如果当前节点的值 严格小于 前一个节点和后一个节点#xff0c;…2058. 找出临界点之间的最小和最大距离
链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。
如果当前节点的值 严格大于 前一个节点和后一个节点那么这个节点就是一个 局部极大值点 。
如果当前节点的值 严格小于 前一个节点和后一个节点那么这个节点就是一个 局部极小值点 。
注意节点只有在同时存在前一个节点和后一个节点的情况下才能成为一个 局部极大值点 / 极小值点 。
给你一个链表 head 返回一个长度为 2 的数组 [minDistance, maxDistance] 其中 minDistance 是任意两个不同临界点之间的最小距离maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个则返回 [-1-1] 。
示例 1 输入head [3,1] 输出[-1,-1] 解释链表 [3,1] 中不存在临界点。
示例 2 输入head [5,3,1,2,5,1,2] 输出[1,3] 解释存在三个临界点
[5,3,1,2,5,1,2]第三个节点是一个局部极小值点因为 1 比 3 和 2 小。[5,3,1,2,5,1,2]第五个节点是一个局部极大值点因为 5 比 2 和 1 大。[5,3,1,2,5,1,2]第六个节点是一个局部极小值点因为 1 比 5 和 2 小。 第五个节点和第六个节点之间距离最小。minDistance 6 - 5 1 。 第三个节点和第六个节点之间距离最大。maxDistance 6 - 3 3 。示例 3 输入head [1,3,2,2,3,2,2,2,7] 输出[3,3] 解释存在两个临界点
[1,3,2,2,3,2,2,2,7]第二个节点是一个局部极大值点因为 3 比 1 和 2 大。[1,3,2,2,3,2,2,2,7]第五个节点是一个局部极大值点因为 3 比 2 和 2 大。 最小和最大距离都存在于第二个节点和第五个节点之间。 因此minDistance 和 maxDistance 是 5 - 2 3 。 注意最后一个节点不算一个局部极大值点因为它之后就没有节点了。示例 4 输入head [2,3,3,2] 输出[-1,-1] 解释链表 [2,3,3,2] 中不存在临界点。
提示
链表中节点的数量在范围 [2, 10510^5105] 内1 Node.val 10510^5105
解题思路
维护当前遍历节点的前两个节点的值加上当前节点每次我们可以遍历到三个值因此我们就可以判断第二个节点 是否为局部极大值点 或 局部极小值点了将每个节点编号使用数组存储临界点之间的下标遍历数组是任意两个不同临界点之间的最小距离两个不同临界点之间的最大距离为数组首尾元素相减的差值
代码
/*** 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:vectorint nodesBetweenCriticalPoints(ListNode *head) {if (head nullptr||head-next nullptr)return vectorint{-1,-1};int f(head-val),s(head-next-val);ListNode *hhead-next-next;int i(2);vectorint idx;while (h! nullptr){if ((sh-valsf)||(sh-valsf))idx.push_back(i);fs;sh-val;hh-next;i;}if (idx.size()1)return vectorint{-1,-1};int midx[idx.size()-1]-idx[0];for (int j 1; j idx.size() ; j) {mmin(idx[j]-idx[j-1],m);}return vectorint{m,idx[idx.size()-1]-idx[0]};}
};
