{"id":8664,"date":"2021-11-03T23:48:43","date_gmt":"2021-11-04T06:48:43","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8664"},"modified":"2021-11-03T23:48:44","modified_gmt":"2021-11-04T06:48:44","slug":"leetcode-2058-find-the-minimum-and-maximum-number-of-nodes-between-critical-points","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-2058-find-the-minimum-and-maximum-number-of-nodes-between-critical-points\/","title":{"rendered":"LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points"},"content":{"rendered":"\n

A critical point<\/strong> in a linked list is defined as either<\/strong> a local maxima<\/strong> or a local minima<\/strong>.<\/p>\n\n\n\n

A node is a local maxima<\/strong> if the current node has a value strictly greater<\/strong> than the previous node and the next node.<\/p>\n\n\n\n

A node is a local minima<\/strong> if the current node has a value strictly smaller<\/strong> than the previous node and the next node.<\/p>\n\n\n\n

Note that a node can only be a local maxima\/minima if there exists both<\/strong> a previous node and a next node.<\/p>\n\n\n\n

Given a linked list head<\/code>, return an array of length 2 containing <\/em>[minDistance, maxDistance]<\/code> where <\/em>minDistance<\/code> is the minimum distance<\/strong> between any two distinct<\/strong> critical points and <\/em>maxDistance<\/code> is the maximum distance<\/strong> between any two distinct<\/strong> critical points. If there are fewer<\/strong> than two critical points, return <\/em>[-1, -1]<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> head = [3,1]\nOutput:<\/strong> [-1,-1]\nExplanation:<\/strong> There are no critical points in [3,1].\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> head = [5,3,1,2,5,1,2]\nOutput:<\/strong> [1,3]\nExplanation:<\/strong> There are three critical points:\n- [5,3,1<\/u><\/strong>,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.\n- [5,3,1,2,5<\/strong>,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.\n- [5,3,1,2,5,1<\/strong>,2]: The sixth node is a local minima because 1 is less than 5 and 2.\nThe minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.\nThe maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> head = [1,3,2,2,3,2,2,2,7]\nOutput:<\/strong> [3,3]\nExplanation:<\/strong> There are two critical points:\n- [1,3<\/strong>,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.\n- [1,3,2,2,3<\/strong>,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.\nBoth the minimum and maximum distances are between the second and the fifth node.\nThus, minDistance and maxDistance is 5 - 2 = 3.\nNote that the last node is not considered a local maxima because it does not have a next node.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> head = [2,3,3,2]\nOutput:<\/strong> [-1,-1]\nExplanation:<\/strong> There are no critical points in [2,3,3,2].\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • The number of nodes in the list is in the range [2, 105<\/sup>]<\/code>.<\/li>
  • 1 <= Node.val <= 105<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: One Pass<\/strong><\/h2>\n\n\n\n
    Track the first and last critical points.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector nodesBetweenCriticalPoints(ListNode* head) {    \n    ListNode* p = nullptr;\n    int min_dist = INT_MAX;\n    int max_dist = INT_MIN;    \n    for (int i = 0, l = -1, r = -1; head; ++i, p = head, head = head->next) {\n      if (p && head->next) {\n        if ((head->val > p->val && head->val > head->next->val) \n            || (head->val < p->val && head->val < head->next->val)) {\n          if (r != -1) {\n            min_dist = min(min_dist, i - r);\n            max_dist = max(max_dist, i - l);\n          } else {\n            l = i;\n          }          \n          r = i;          \n        }\n      }\n    }\n    return { min_dist == INT_MAX ? -1 : min_dist, \n             max_dist == INT_MIN ? -1 : max_dist };\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[50],"tags":[],"class_list":["post-8664","post","type-post","status-publish","format-standard","hentry","category-list","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8664","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8664"}],"version-history":[{"count":1,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8664\/revisions"}],"predecessor-version":[{"id":8665,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8664\/revisions\/8665"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8664"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8664"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8664"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}