{"id":6701,"date":"2020-05-03T21:21:37","date_gmt":"2020-05-04T04:21:37","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6701"},"modified":"2020-05-08T08:54:03","modified_gmt":"2020-05-08T15:54:03","slug":"leetcode-1438-longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/queue\/leetcode-1438-longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit EP323\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/p8-f0_CwWLk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given an&nbsp;array of integers&nbsp;<code>nums<\/code>&nbsp;and an&nbsp;integer&nbsp;<code>limit<\/code>, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to&nbsp;<code>limit<\/code><em>.<\/em><\/p>\n\n\n\n<p>In case there is no subarray satisfying the given condition return 0.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [8,2,4,7], limit = 4\n<strong>Output:<\/strong> 2 \n<strong>Explanation:<\/strong> All subarrays are: \n[8] with maximum absolute diff |8-8| = 0 &lt;= 4.\n[8,2] with maximum absolute diff |8-2| = 6 &gt; 4. \n[8,2,4] with maximum absolute diff |8-2| = 6 &gt; 4.\n[8,2,4,7] with maximum absolute diff |8-2| = 6 &gt; 4.\n[2] with maximum absolute diff |2-2| = 0 &lt;= 4.\n[2,4] with maximum absolute diff |2-4| = 2 &lt;= 4.\n[2,4,7] with maximum absolute diff |2-7| = 5 &gt; 4.\n[4] with maximum absolute diff |4-4| = 0 &lt;= 4.\n[4,7] with maximum absolute diff |4-7| = 3 &lt;= 4.\n[7] with maximum absolute diff |7-7| = 0 &lt;= 4. \nTherefore, the size of the longest subarray is 2.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [10,1,2,4,7,2], limit = 5\n<strong>Output:<\/strong> 4 \n<strong>Explanation:<\/strong> The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 &lt;= 5.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [4,2,2,2,4,4,2,2], limit = 0\n<strong>Output:<\/strong> 3\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 10^5<\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 10^9<\/code><\/li><li><code>0 &lt;= limit &lt;= 10^9<\/code><\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1438-ep323-1.png\" alt=\"\" class=\"wp-image-6706\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1438-ep323-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1438-ep323-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1438-ep323-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1438-ep323-2.png\" alt=\"\" class=\"wp-image-6707\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1438-ep323-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1438-ep323-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1438-ep323-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Sliding Window + TreeSet<\/strong><\/h2>\n\n\n\n<p>Use a treeset to maintain a range of [l, r] such that max(nums[l~r]) &#8211; min(nums[l~r]) &lt;= limit.<br>Every time, we add nums[r] into the tree, and move l towards r to keep the max diff under limit.<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int longestSubarray(vector<int>& nums, int limit) {\n    multiset<int> s;\n    int l = 0;\n    int ans = 0;\n    for (int r = 0; r < nums.size(); ++r) {\n      s.insert(nums[r]);\n      while (*rbegin(s) - *begin(s) > limit)\n        s.erase(s.equal_range(nums[l++]).first);\n      ans = max(ans, r - l + 1);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Dual Monotonic Queue<\/strong><\/h2>\n\n\n\n<p>Similar to <a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1425-constrained-subset-sum\/\">https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1425-constrained-subset-sum\/<\/a><\/p>\n\n\n\n<p>We want to maintain a range [l, r] that max(nums[l~r]) &#8211; min(nums[l~r]) &lt;= limit, to track the max\/min of a range efficiently we could use monotonic queue. One for max and one for min.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int longestSubarray(vector<int>& nums, int limit) {\n    deque<int> max_q;\n    deque<int> min_q;\n    int ans = 0;\n    int l = 0;\n    for (int r = 0; r < nums.size(); ++r) {\n      while (!min_q.empty() &#038;&#038; nums[r] < min_q.back()) \n        min_q.pop_back();\n      while (!max_q.empty() &#038;&#038; nums[r] > max_q.back()) \n        max_q.pop_back();\n      min_q.push_back(nums[r]);\n      max_q.push_back(nums[r]);\n      while (max_q.front() - min_q.front() > limit) {\n        if (max_q.front() == nums[l]) max_q.pop_front();\n        if (min_q.front() == nums[l]) min_q.pop_front();\n        ++l;\n      }\n      ans = max(ans, r - l + 1);\n    }\n    return ans;\n  }\n};\n\n\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an&nbsp;array of integers&nbsp;nums&nbsp;and an&nbsp;integer&nbsp;limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[429],"tags":[177,587,335],"class_list":["post-6701","post","type-post","status-publish","format-standard","hentry","category-queue","tag-medium","tag-monotonic-queue","tag-multiset","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6701","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=6701"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6701\/revisions"}],"predecessor-version":[{"id":6730,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6701\/revisions\/6730"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6701"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6701"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6701"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}