{"id":9162,"date":"2021-12-12T15:20:21","date_gmt":"2021-12-12T23:20:21","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9162"},"modified":"2021-12-12T15:42:11","modified_gmt":"2021-12-12T23:42:11","slug":"leetcode-2104-sum-of-subarray-ranges","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2104-sum-of-subarray-ranges\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2104. Sum of Subarray Ranges"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\"><strong><a href=\"https:\/\/leetcode.com\/problems\/sum-of-subarray-ranges\/\">Problem<\/a><\/strong><\/h2>\n\n\n\n<p><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 0: Brute force<\/strong> <span class=\"has-inline-color has-vivid-red-color\"><strong>[TLE]<\/strong><\/span><\/h2>\n\n\n\n<p>Enumerate all subarrays, for each one, find min and max.<\/p>\n\n\n\n<p>Time complexity: O(n<sup>3<\/sup>)<br>Space complexity: O(1)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Prefix min\/max<\/strong><\/h2>\n\n\n\n<p>We can use prefix technique to extend the array while keep tracking the min\/max of the subarray.<\/p>\n\n\n\n<p>Time complexity: O(n<sup>2<\/sup>)<br>Space complexity: O(1)<\/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  long long subArrayRanges(vector<int>& nums) {\n    const int n = nums.size();    \n    long long ans = 0;\n    for (int i = 0; i < n; ++i) {\n      int lo = nums[i];\n      int hi = nums[i];\n      for (int j = i + 1; j < n; ++j) {\n        lo = min(lo, nums[j]);\n        hi = max(hi, nums[j]);\n        ans += (hi - lo);\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Monotonic stack<\/strong><\/h2>\n\n\n\n<p>This problem can be reduced to <a href=\"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-907-sum-of-subarray-minimums\/\" data-type=\"post\" data-id=\"3987\">\u82b1\u82b1\u9171 LeetCode 907. Sum of Subarray Minimums<\/a><\/p>\n\n\n\n<p>Just need to run twice one for sum of mins and another for sum of maxs.<\/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  long long subArrayRanges(vector<int>& nums) {\n    const int n = nums.size();\n    auto sumOf = [&](function<bool(int, int)> op) {\n      long long ans = 0;\n      stack<int> s;\n      for (long long i = 0; i <= n; ++i) {\n        while (!s.empty() and (i == n or op(nums[s.top()], nums[i]))) {\n          long long k = s.top(); s.pop();\n          long long j = s.empty() ? -1 : s.top();\n          ans += nums[k] * (i - k) * (k - j);\n        }\n        s.push(i);\n      }\n      return ans;\n    };\n    return sumOf(less<int>()) - sumOf(greater<int>());\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem Solution 0: Brute force [TLE] Enumerate all subarrays, for each one, find min and max. Time complexity: O(n3)Space complexity: O(1) Solution 1: Prefix min\/max&#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],"tags":[20,177,41],"class_list":["post-9162","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-medium","tag-subarray","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9162","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=9162"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9162\/revisions"}],"predecessor-version":[{"id":9167,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9162\/revisions\/9167"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9162"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9162"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9162"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}