Question

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

中文文档

Description

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

Solutions

Solution 1

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#     self.val = val
#     self.next = next
class Solution:
  def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
    prev, curr = head, head.next
    first = last = None
    i = 1
    ans = [inf, -inf]
    while curr.next:
      if curr.val < min(prev.val, curr.next.val) or curr.val > max(
        prev.val, curr.next.val
      ):
        if last is None:
          first = last = i
        else:
          ans[0] = min(ans[0], i - last)
          ans[1] = i - first
          last = i
      i += 1
      prev, curr = curr, curr.next
    return ans if first != last else [-1, -1]

/**
 * 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) {
    ListNode prev = head;
    ListNode curr = head.next;
    int first = 0, last = 0;
    int i = 1;
    int[] ans = new int[] {Integer.MAX_VALUE, Integer.MIN_VALUE};
    while (curr.next != null) {
      if (curr.val < Math.min(prev.val, curr.next.val)
        || curr.val > Math.max(prev.val, curr.next.val)) {
        if (last == 0) {
          first = i;
          last = i;
        } else {
          ans[0] = Math.min(ans[0], i - last);
          ans[1] = i - first;
          last = i;
        }
      }
      ++i;
      prev = curr;
      curr = curr.next;
    }
    return first == last ? new int[] {-1, -1} : ans;
  }
}

/**
 * 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) {
    ListNode* prev = head;
    ListNode* curr = head->next;
    int first = 0, last = 0;
    int i = 1;
    vector<int> ans(2, INT_MAX);
    while (curr->next) {
      if (curr->val < min(prev->val, curr->next->val) || curr->val > max(prev->val, curr->next->val)) {
        if (last == 0)
          first = i;
        else {
          ans[0] = min(ans[0], i - last);
          ans[1] = i - first;
        }
        last = i;
      }
      ++i;
      prev = curr;
      curr = curr->next;
    }
    if (first == last) return {-1, -1};
    return ans;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func nodesBetweenCriticalPoints(head *ListNode) []int {
  prev, curr := head, head.Next
  first, last := 0, 0
  i := 1
  ans := []int{math.MaxInt32, 0}
  for curr.Next != nil {
    if curr.Val < min(prev.Val, curr.Next.Val) || curr.Val > max(prev.Val, curr.Next.Val) {
      if last == 0 {
        first, last = i, i
      } else {
        ans[0] = min(ans[0], i-last)
        ans[1] = i - first
        last = i
      }
    }
    i++
    prev, curr = curr, curr.Next
  }
  if first == last {
    return []int{-1, -1}
  }
  return ans
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function nodesBetweenCriticalPoints(head: ListNode | null): number[] {
  let idx = 1;
  let pre = head.val;
  head = head.next;
  let nums = [];
  while (head.next != null) {
    let val = head.val,
      post = head.next.val;
    if (pre < val && val > post) {
      nums.push(idx);
    }
    if (pre > val && val < post) {
      nums.push(idx);
    }
    pre = val;
    idx++;
    head = head.next;
  }
  let n = nums.length;
  if (n < 2) return [-1, -1];
  let min = Infinity;
  for (let i = 1; i < n; i++) {
    min = Math.min(nums[i] - nums[i - 1], min);
  }
  return [min, nums[n - 1] - nums[0]];
}