{"id":1173,"date":"2017-12-10T16:19:22","date_gmt":"2017-12-11T00:19:22","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1173"},"modified":"2017-12-11T00:07:52","modified_gmt":"2017-12-11T08:07:52","slug":"leetcode-164-maximum-gap","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/difficulty\/hard\/leetcode-164-maximum-gap\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 164. Maximum Gap"},"content":{"rendered":"<p><a href=\"https:\/\/leetcode.com\/problems\/maximum-gap\/description\/\">https:\/\/leetcode.com\/problems\/maximum-gap\/description\/<\/a><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given an unsorted array, find the maximum difference between the successive elements in its sorted form.<\/p>\n<p>Try to solve it in linear time\/space.<\/p>\n<p>Return 0 if the array contains less than 2 elements.<\/p>\n<p>You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.<\/p>\n<p>\u9898\u76ee\u5927\u610f:<\/p>\n<p>\u7ed9\u4f60\u4e00\u4e2a\u6ca1\u6709\u6392\u5e8f\u7684\u6b63\u6574\u6570\u6570\u7ec4\u3002\u8f93\u51fa\u6392\u5e8f\u540e\uff0c\u76f8\u90bb\u5143\u7d20\u7684\u5dee\u7684\u6700\u5927\u503c(Max Gap)\u3002\u9700\u8981\u5728\u7ebf\u6027\u65f6\u95f4\u5185\u89e3\u51b3\u3002<\/p>\n<p><strong>Example:<\/strong><\/p>\n<p><span style=\"font-weight: 400;\">Input: \u00a0[5, 0, 4, 2, 12, 10]<\/span><\/p>\n<p>Output: 5<\/p>\n<p><strong>Explanation:\u00a0<\/strong><\/p>\n<p><span style=\"font-weight: 400;\">Sorted: [0, 2, 4, 5, 10, 12]<\/span><\/p>\n<p>max gap is 10 &#8211; 5 = 5<\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Bucket sort. Use n buckets to store all the numbers. For each bucket, only track the min \/ max value.<\/p>\n<p>\u6876\u6392\u5e8f\u3002\u7528n\u4e2a\u6876\u6765\u5b58\u653e\u6570\u5b57\u3002\u5bf9\u4e8e\u6bcf\u4e2a\u6876\uff0c\u53ea\u8ddf\u8e2a\u5b58\u50a8\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\u3002<\/p>\n<p>max gap must come from two &#8220;adjacent&#8221; buckets, b[i], b[j], j &gt; i, b[i+1] &#8230; b[j &#8211; 1] must be empty.<\/p>\n<p>max gap \u53ea\u53ef\u80fd\u6765\u81ea&#8221;\u76f8\u90bb&#8221;\u7684\u4e24\u4e2a\u6876 b[i] \u548c b[j], j &gt; i, b[i] \u548c b[j] \u4e4b\u95f4\u7684\u6876\uff08\u5982\u679c\u6709\uff09\u5fc5\u987b\u4e3a\u7a7a\u3002<\/p>\n<p>max gap = b[j].min &#8211; b[i].min<\/p>\n<p>Time complexity: O(n)<\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6: O(n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<p>\u7a7a\u95f4\u590d\u6742\u5ea6: O(n)<\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 6 ms\r\nclass Solution {\r\npublic:\r\n    int maximumGap(vector&lt;int&gt;&amp; nums) {\r\n        const int n = nums.size();\r\n        if (n &lt;= 1) return 0;\r\n        \r\n        const auto mm = minmax_element(nums.begin(), nums.end());\r\n        const int range = *mm.second - *mm.first;\r\n        const int bin_size = range \/ n + 1;\r\n        vector&lt;int&gt; min_vals(n, INT_MAX);\r\n        vector&lt;int&gt; max_vals(n, INT_MIN);\r\n        for (const int num : nums) {\r\n            const int index = (num - *mm.first) \/ bin_size;\r\n            min_vals[index] = min(min_vals[index], num);\r\n            max_vals[index] = max(max_vals[index], num);\r\n        }\r\n        \r\n        int max_gap = 0;\r\n        int prev_max = max_vals[0];\r\n        for (int i = 1; i &lt; n; ++i) {\r\n            if (min_vals[i] != INT_MAX) {\r\n                max_gap = max(max_gap, min_vals[i] - prev_max);\r\n                prev_max = max_vals[i];\r\n            }\r\n        }\r\n        return max_gap;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/maximum-gap\/description\/ Problem: Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time\/space.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,165],"tags":[115,15],"class_list":["post-1173","post","type-post","status-publish","format-standard","hentry","category-array","category-hard","tag-bucket","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1173","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=1173"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1173\/revisions"}],"predecessor-version":[{"id":1175,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1173\/revisions\/1175"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1173"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1173"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}