Package g2001_2100.s2058_find_the_minimum_and_maximum_number_of_nodes_between_critical_points

Class Solution

java.lang.Object
g2001_2100.s2058_find_the_minimum_and_maximum_number_of_nodes_between_critical_points.Solution
public class Solution extends Object
2058 - Find the Minimum and Maximum Number of Nodes Between Critical Points.<p>Medium</p> <p>A <strong>critical point</strong> in a linked list is defined as <strong>either</strong> a <strong>local maxima</strong> or a <strong>local minima</strong>.</p> <p>A node is a <strong>local maxima</strong> if the current node has a value <strong>strictly greater</strong> than the previous node and the next node.</p> <p>A node is a <strong>local minima</strong> if the current node has a value <strong>strictly smaller</strong> than the previous node and the next node.</p> <p>Note that a node can only be a local maxima/minima if there exists <strong>both</strong> a previous node and a next node.</p> <p>Given a linked list <code>head</code>, return <em>an array of length 2 containing</em> <code>[minDistance, maxDistance]</code> <em>where</em> <code>minDistance</code> <em>is the <strong>minimum distance</strong> between <strong>any two distinct</strong> critical points and</em> <code>maxDistance</code> <em>is the <strong>maximum distance</strong> between <strong>any two distinct</strong> critical points. If there are <strong>fewer</strong> than two critical points, return</em> <code>[-1, -1]</code>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/10/13/a1.png" alt="" /></p> <p><strong>Input:</strong> head = [3,1]</p> <p><strong>Output:</strong> [-1,-1]</p> <p><strong>Explanation:</strong> There are no critical points in [3,1].</p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/10/13/a2.png" alt="" /></p> <p><strong>Input:</strong> head = [5,3,1,2,5,1,2]</p> <p><strong>Output:</strong> [1,3]</p> <p><strong>Explanation:</strong> There are three critical points:</p> <ul> <li> <p>[5,3, <strong>1</strong> ,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.</p> </li> <li> <p>[5,3,1,2, <strong>5</strong> ,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.</p> </li> <li> <p>[5,3,1,2,5, <strong>1</strong> ,2]: The sixth node is a local minima because 1 is less than 5 and 2.</p> </li> </ul> <p>The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.</p> <p>The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.</p> <p><strong>Example 3:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/10/14/a5.png" alt="" /></p> <p><strong>Input:</strong> head = [1,3,2,2,3,2,2,2,7]</p> <p><strong>Output:</strong> [3,3]</p> <p><strong>Explanation:</strong> There are two critical points:</p> <ul> <li> <p>[1, <strong>3</strong> ,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.</p> </li> <li> <p>[1,3,2,2, <strong>3</strong> ,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.</p> </li> </ul> <p>Both the minimum and maximum distances are between the second and the fifth node.</p> <p>Thus, minDistance and maxDistance is 5 - 2 = 3.</p> <p>Note that the last node is not considered a local maxima because it does not have a next node.</p> <p><strong>Constraints:</strong></p> <ul> <li>The number of nodes in the list is in the range <code>[2, 10<sup>5</sup>]</code>.</li> <li><code>1 <= Node.val <= 10<sup>5</sup></code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • nodesBetweenCriticalPoints

      public int[] nodesBetweenCriticalPoints(ListNode head)