{"id":3987,"date":"2018-09-16T00:35:24","date_gmt":"2018-09-16T07:35:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3987"},"modified":"2018-09-16T02:02:13","modified_gmt":"2018-09-16T09:02:13","slug":"leetcode-907-sum-of-subarray-minimums","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-907-sum-of-subarray-minimums\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 907. Sum of Subarray Minimums"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given an array of integers\u00a0A<\/code>, find the sum of\u00a0min(B)<\/code>, where\u00a0B<\/code>\u00a0ranges over\u00a0every (contiguous) subarray of\u00a0A<\/code>.<\/p>\n

Since the answer may be large,\u00a0return the answer modulo\u00a010^9 + 7<\/code>.<\/strong><\/p>\n

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

Input: <\/strong>[3,1,2,4]<\/span>\r\nOutput: <\/strong>17<\/span>\r\nExplanation:<\/strong> Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. \r\nMinimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.\u00a0 Sum is 17.<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= A.length <= 30000<\/code><\/li>\n
  2. 1 <= A[i] <= 30000<\/code><\/li>\n<\/ol>\n
    Idea<\/strong><\/h1>\n
      \n
    1. order matters, unlike\u00a0\u82b1\u82b1\u9171 LeetCode 898. Bitwise ORs of Subarrays<\/a> we can not sort the numbers in this problem.\n
        \n
      1. e.g. sumSubarrayMins([3, 1, 2, 4]) !=sumSubarrayMins([1, 2, 3, 4]) since the first one will not have a subarray of [3,4].<\/li>\n<\/ol>\n<\/li>\n
      2. For A[i], assuming there are L numbers that are greater than A[i] in range A[0] ~ A[i – 1], and there are R numbers that are greater or equal than A[i] in the range of A[i+1] ~ A[n – 1]. Thus A[i] will be the min of (L + 1) * (R + 1) subsequences.\n
          \n
        1. e.g. A =\u00a0[3,1,2,4], A[1] = 1, L = 1, R = 2, there are (1 + 1) * (2 + 1) = 6 subsequences are 1 is the min number. [3,1], [3,1,2], [3,1,2,4], [1], [1,2], [1,2,4]<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n
          Solution 1: Brute Force<\/strong><\/h1>\n
          Time complexity: O(n^2)<\/p>\n
          Space complexity: O(1)<\/p>\n
          \n
          C++<\/h2>\n
          \n\n
          \/\/ Author: Huahua, 1504 ms\r\nclass Solution {\r\npublic:\r\n  int sumSubarrayMins(vector<int>& A) {\r\n    constexpr int kMod = 1e9 + 7;\r\n    int ans = 0;\r\n    for (int i = 0; i < A.size(); ++i) {\r\n      int left = 0;\r\n      for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left);\r\n      int right = 0;\r\n      for (int j = i + 1; j < A.size() && A[j] >= A[i]; ++j, ++right);\r\n      ans = (ans + static_cast<long>(A[i]) * (left + 1) * (right + 1)) % kMod;\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div>
          Java<\/h2>\n
          \n\n
          \/\/ Author: Huahua, 511 ms\r\nclass Solution {\r\n  public int sumSubarrayMins(int[] A) {\r\n    final int kMod = 1000000007;\r\n    final int n = A.length;\r\n    int ans = 0;\r\n    for (int i = 0; i < n; ++i) {\r\n      int left = 0;\r\n      for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left);\r\n      int right = 0;\r\n      for (int j = i + 1; j < n && A[j] >= A[i]; ++j, ++right);\r\n      ans = (int)((ans + (long)A[i] * (left + 1) * (right + 1)) % kMod);\r\n    }\r\n    return ans;\r\n  }\r\n}<\/pre>\n\n<\/div>
          Python3 (TLE)<\/h2>\n
          \n\n
          # Author: Huahua, 96\/100 passed\r\nclass Solution:\r\n  def sumSubarrayMins(self, A):\r\n    kMod = 10 ** 9 + 7\r\n    n = len(A)\r\n    ans = 0\r\n    for i in range(n):\r\n      left, right = 1, 1\r\n      while i - left >= 0 and A[i - left] > A[i]:\r\n        left += 1\r\n      while i + right < n and A[i + right] >= A[i]:\r\n        right += 1\r\n      ans += A[i] * left * right\r\n    return ans % kMod\r\n      \r\n<\/pre>\n<\/div><\/div>\n
          Solution2 : Monotonic Stack<\/strong><\/h1>\n
          Time complexity: O(n)<\/p>\n
          Space complexity: O(n)<\/p>\n
          We can use a monotonic stack to compute left[i] and right[i] similar to\u00a0\u82b1\u82b1\u9171 LeetCode 901. Online Stock Span<\/a><\/p>\n
          \n
          C++<\/h2>\n
          \n\n
          \/\/ Author: Huahua, 60 ms\r\nclass Solution {\r\npublic:\r\n  int sumSubarrayMins(vector<int>& A) {\r\n    constexpr int kMod = 1e9 + 7;\r\n    const int n = A.size();\r\n    vector<int> left(n);\r\n    vector<int> right(n);\r\n    stack<pair<int, int>> s;    \r\n    int ans = 0;\r\n    for (int i = 0; i < n; ++i) {\r\n      int len = 1;\r\n      while (!s.empty() && s.top().first > A[i]) {\r\n        len += s.top().second; s.pop();\r\n      }\r\n      s.emplace(A[i], len);\r\n      left[i] = len;\r\n    }\r\n    while (!s.empty()) s.pop();\r\n    for (int i = n - 1; i >= 0; --i) {\r\n      int len = 1;\r\n      while (!s.empty() && s.top().first >= A[i]) {\r\n        len += s.top().second; s.pop();\r\n      }\r\n      s.emplace(A[i], len);\r\n      right[i] = len;\r\n    } \r\n    for (int i = 0; i < n; ++i)\r\n      ans = (ans + static_cast<long>(left[i]) * A[i] * right[i]) % kMod;    \r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div>
          Java<\/h2>\n
          \n\n
          \/\/ Author: Huahua, 154 ms\r\nclass Solution {\r\n  public int sumSubarrayMins(int[] A) {\r\n    final int kMod = 1000000007;\r\n    final int n = A.length;\r\n    Stack<Integer> nums = new Stack<>();\r\n    Stack<Integer> lens = new Stack<>();\r\n    int[] left = new int[n];\r\n    int[] right = new int[n];\r\n    int ans = 0;\r\n    \r\n    for (int i = 0; i < n; ++i) {\r\n      int len = 1;\r\n      while (!nums.empty() && nums.peek() > A[i]) {\r\n        len += lens.pop(); nums.pop();\r\n      }\r\n      nums.push(A[i]);\r\n      lens.push(len);\r\n      left[i] = len;\r\n    }\r\n    nums.clear();\r\n    lens.clear();\r\n    for (int i = n - 1; i >= 0; --i) {\r\n      int len = 1;\r\n      while (!nums.empty() && nums.peek() >= A[i]) {\r\n        len += lens.pop(); nums.pop();\r\n      }\r\n      nums.push(A[i]);\r\n      lens.push(len);\r\n      right[i] = len;\r\n    }\r\n    \r\n    for (int i = 0; i < n; ++i)\r\n      ans = (int)(ans + (long)A[i] * left[i] * right[i]) % kMod;\r\n    \r\n    return ans;\r\n  }\r\n}<\/pre>\n\n<\/div>
          Python3<\/h2>\n
          \n\n
          # Author: Huahua, 376 ms\r\nclass Solution:\r\n  def sumSubarrayMins(self, A):\r\n    kMod = 10 ** 9 + 7\r\n    n = len(A)    \r\n    s, left, right = [], [1] * n, [1] * n\r\n    for i in range(n):      \r\n      while s and s[-1][0] > A[i]:        \r\n        left[i] += s.pop()[1]\r\n      s.append((A[i], left[i]))      \r\n    s = []\r\n    for i in range(n - 1, -1, -1):      \r\n      while s and s[-1][0] >= A[i]:        \r\n        right[i] += s.pop()[1]\r\n      s.append((A[i], right[i]))         \r\n    ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod\r\n    return ans<\/pre>\n\n<\/div>
          Python3 V2<\/h2>\n
          \n\n
          # Author: Huahua, 366 ms\r\nclass Solution:\r\n  def sumSubarrayMins(self, A):\r\n    kMod = 10 ** 9 + 7\r\n    n = len(A)\r\n    left, right = [1] * n, [1] * n\r\n    def fillLength(counts, start, end, step):      \r\n      s = []\r\n      for i in range(start, end, step):        \r\n        num = A[i] if step > 0 else A[i] - 1        \r\n        while s and s[-1][0] > num:\r\n          counts[i] += s.pop()[1]\r\n        s.append((A[i], counts[i]))\r\n    fillLength(left, 0, n, 1)\r\n    fillLength(right, n - 1, -1, -1)\r\n    ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod\r\n    return ans<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
          Problem Given an array of integers\u00a0A, find the sum of\u00a0min(B), where\u00a0B\u00a0ranges over\u00a0every (contiguous) subarray of\u00a0A. Since the answer may be large,\u00a0return the answer modulo\u00a010^9 +…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[407],"tags":[217,180,41],"class_list":["post-3987","post","type-post","status-publish","format-standard","hentry","category-stack","tag-hard","tag-stack","tag-subarray","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3987","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=3987"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3987\/revisions"}],"predecessor-version":[{"id":3997,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3987\/revisions\/3997"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3987"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3987"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3987"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}