[LeetCode] 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].

Example 1:

Input: head = [3,1]
Output: [-1,-1]
Explanation: There are no critical points in [3,1].

Example 2:

Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: There are three critical points:

• [5,3,1,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
• [5,3,1,2,5,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
• [5,3,1,2,5,1,2]: The sixth node is a local minima because 1 is less than 5 and 2.
  The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
  The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.

Example 3:

Input: head = [1,3,2,2,3,2,2,2,7]
Output: [3,3]
Explanation: There are two critical points:

• [1,3,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.
• [1,3,2,2,3,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.
  Both the minimum and maximum distances are between the second and the fifth node.
  Thus, minDistance and maxDistance is 5 - 2 = 3.
  Note that the last node is not considered a local maxima because it does not have a next node.

Constraints:
The number of nodes in the list is in the range [2, 105].
1 <= Node.val <= 105

找出临界点之间的最小和最大距离。

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

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

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

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

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

思路

这道题不涉及算法，需要把题目意思读懂。题目给了一个链表，需要我们找出其中所有的临界点。临界点的定义是局部极大值点和局部极小值点。所以思路是遍历链表，找出所有的临界点，并记录他们在原链表中的位置。然后根据临界点的位置计算出最小和最大距离。

复杂度

时间O(n)
空间O(n)

代码

Java实现

/**
 * Definition for singly-linked list.
 * 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 {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        // corner case
        if (head == null || head.next == null || head.next.next == null) {
            return new int[] { -1, -1 };
        }

        // normal case
        int index = 1;
        int prev = head.val;
        List<Integer> indexes = new ArrayList<>();
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val > prev && cur.val > cur.next.val || cur.val < prev && cur.val < cur.next.val) {
                indexes.add(index);
            }
            prev = cur.val;
            cur = cur.next;
            index++;
        }

        // corner case
        if (indexes.size() < 2) {
            return new int[] { -1, -1 };
        }
        int n = indexes.size();
        int min = Integer.MAX_VALUE;
        int max = indexes.get(n - 1) - indexes.get(0);
        for (int i = 1; i < n; i++) {
            min = Math.min(min, indexes.get(i) - indexes.get(i - 1));
        }
        return new int[] { min, max };
    }
}