LeetCode 2058.找出临界点之间的最小和最大距离
题目:
链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。
如果当前节点的值 严格大于 前一个节点和后一个节点,那么这个节点就是一个 局部极大值点 。
如果当前节点的值 严格小于 前一个节点和后一个节点,那么这个节点就是一个 局部极小值点 。
注意:节点只有在同时存在前一个节点和后一个节点的情况下,才能成为一个 局部极大值点 / 极小值点 。
给你一个链表 head
,返回一个长度为 2 的数组 [minDistance, maxDistance]
,其中 minDistance
是任意两个不同临界点之间的最小距离,maxDistance
是任意两个不同临界点之间的最大距离。如果临界点少于两个,则返回 [-1,-1]
。
思路:方法一:遍历链表,把临界点存入list,再次遍历,求出最小最大距离
方法二:用几个变量替代 list
代码:
class Solution { // 方法一
public int[] nodesBetweenCriticalPoints(ListNode head) {
List<Integer> list = new ArrayList<>();
int k = 1;
int minDistance = Integer.MAX_VALUE;
ListNode front = head;
head = head.next;
while (head.next != null) {
int front_v = front.val;
int mid_v = head.val;
int after_v = head.next.val;
if ((mid_v > front_v && mid_v > after_v) || (mid_v < front_v && mid_v < after_v))
list.add(k);
front = head;
head = head.next;
k = k + 1;
}
if (list.size() < 2)
return new int[] {-1, -1};
for (int i = 1; i < list.size(); i++) {
minDistance = Math.min(minDistance, list.get(i) - list.get(i - 1));
}
int maxDistance = list.get(list.size() - 1) - list.get(0);
return new int[] {minDistance, maxDistance};
}
}
class Solution { // 方法二
public int[] nodesBetweenCriticalPoints(ListNode head) {
int[] result = new int[2];
result[0] = Integer.MAX_VALUE;
result[1] = -1;
//第一个极值的位置(求最大值使用)
int first = 0;
//上一个极值的位置(求最小值使用)
int previous = 0;
ListNode slow = head;
ListNode fast = head.next.next;
int i = 1;
//循环结束之后,previous就是最后一个极值的位置
while (fast!=null){
if((slow.next.val>slow.val && slow.next.val>fast.val)||(slow.next.val<slow.val && slow.next.val<fast.val)){
if(first == 0){
first = i;
previous = i;
}else{
result[0] = Math.min(result[0],i - previous);
previous = i;
}
}
slow = slow.next;
fast = fast.next;
i++;
}
if(first!=previous){
//表明至少两个极值
result[1] = previous - first;
}else{
//0个极值或者1个极值
result[0] = -1;
}
return result;
}
}
性能:
方法一:
时间复杂度o(n)
空间复杂度o(临界点个数)
方法二:
时间复杂度o(n)
空间复杂度o(1)