2058. Find the Minimum and Maximum Number of Nodes Between Critical Points #

题目 #

链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点。

如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个 局部极大值点 。

如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个 局部极小值点 。

注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。

给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1] 。

思路 #

在第一个节点存在的情况下，每遇到一个新的临界点，maxDistance 在原有基础上递增距离，minDistance 重新计算。
maxDistance 是所有临界点分段的距离之和。

代码 #

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    boolean isLocalMaximum(ListNode ptr) {
        return ptr.next.val > ptr.val && ptr.next.val > ptr.next.next.val;
    }
    boolean isLocalMinimum(ListNode ptr) {
        return ptr.next.val < ptr.val && ptr.next.val < ptr.next.next.val;
    }
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        int[] distanceMinMax = new int[]{-1, -1};
        int step = 0;
        ListNode ptr = head, mark = null;
        while (ptr.next.next != null) {
            if (isLocalMaximum(ptr) == null || isLocalMinimum(ptr) == null) {
                if (mark != null) {
                    if (distanceMinMax[0] == -1) distanceMinMax[0] = distanceMinMax[1] = step + 1;
                    else {
                        distanceMinMax[0] = (step + 1) < distanceMinMax[0] ? step + 1: distanceMinMax[0];
                        distanceMinMax[1] += step + 1;
                    }
                }
                ptr = mark = ptr.next;
                step = 0;
            } else {
                ptr = ptr.next;
                step += 1;
            }
        }
        return distanceMinMax;
    }
}