Problem
Given an array of integers A
, find the sum of min(B)
, where B
ranges over every (contiguous) subarray of A
.
Since the answer may be large, return the answer modulo 10^9 + 7
.
Example 1:
Input: [3,1,2,4] Output: 17 Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.
Note:
1 <= A.length <= 30000
1 <= A[i] <= 30000
Idea
- order matters, unlike 花花酱 LeetCode 898. Bitwise ORs of Subarrays we can not sort the numbers in this problem.
- e.g. sumSubarrayMins([3, 1, 2, 4]) !=sumSubarrayMins([1, 2, 3, 4]) since the first one will not have a subarray of [3,4].
- 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.
- e.g. A = [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]
Solution 1: Brute Force
Time complexity: O(n^2)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua, 1504 ms class Solution { public: int sumSubarrayMins(vector<int>& A) { constexpr int kMod = 1e9 + 7; int ans = 0; for (int i = 0; i < A.size(); ++i) { int left = 0; for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left); int right = 0; for (int j = i + 1; j < A.size() && A[j] >= A[i]; ++j, ++right); ans = (ans + static_cast<long>(A[i]) * (left + 1) * (right + 1)) % kMod; } return ans; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua, 511 ms class Solution { public int sumSubarrayMins(int[] A) { final int kMod = 1000000007; final int n = A.length; int ans = 0; for (int i = 0; i < n; ++i) { int left = 0; for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left); int right = 0; for (int j = i + 1; j < n && A[j] >= A[i]; ++j, ++right); ans = (int)((ans + (long)A[i] * (left + 1) * (right + 1)) % kMod); } return ans; } } |
Python3 (TLE)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Author: Huahua, 96/100 passed class Solution: def sumSubarrayMins(self, A): kMod = 10 ** 9 + 7 n = len(A) ans = 0 for i in range(n): left, right = 1, 1 while i - left >= 0 and A[i - left] > A[i]: left += 1 while i + right < n and A[i + right] >= A[i]: right += 1 ans += A[i] * left * right return ans % kMod |
Solution2 : Monotonic Stack
Time complexity: O(n)
Space complexity: O(n)
We can use a monotonic stack to compute left[i] and right[i] similar to 花花酱 LeetCode 901. Online Stock Span
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua, 60 ms class Solution { public: int sumSubarrayMins(vector<int>& A) { constexpr int kMod = 1e9 + 7; const int n = A.size(); vector<int> left(n); vector<int> right(n); stack<pair<int, int>> s; int ans = 0; for (int i = 0; i < n; ++i) { int len = 1; while (!s.empty() && s.top().first > A[i]) { len += s.top().second; s.pop(); } s.emplace(A[i], len); left[i] = len; } while (!s.empty()) s.pop(); for (int i = n - 1; i >= 0; --i) { int len = 1; while (!s.empty() && s.top().first >= A[i]) { len += s.top().second; s.pop(); } s.emplace(A[i], len); right[i] = len; } for (int i = 0; i < n; ++i) ans = (ans + static_cast<long>(left[i]) * A[i] * right[i]) % kMod; return ans; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Author: Huahua, 154 ms class Solution { public int sumSubarrayMins(int[] A) { final int kMod = 1000000007; final int n = A.length; Stack<Integer> nums = new Stack<>(); Stack<Integer> lens = new Stack<>(); int[] left = new int[n]; int[] right = new int[n]; int ans = 0; for (int i = 0; i < n; ++i) { int len = 1; while (!nums.empty() && nums.peek() > A[i]) { len += lens.pop(); nums.pop(); } nums.push(A[i]); lens.push(len); left[i] = len; } nums.clear(); lens.clear(); for (int i = n - 1; i >= 0; --i) { int len = 1; while (!nums.empty() && nums.peek() >= A[i]) { len += lens.pop(); nums.pop(); } nums.push(A[i]); lens.push(len); right[i] = len; } for (int i = 0; i < n; ++i) ans = (int)(ans + (long)A[i] * left[i] * right[i]) % kMod; return ans; } } |
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Author: Huahua, 376 ms class Solution: def sumSubarrayMins(self, A): kMod = 10 ** 9 + 7 n = len(A) s, left, right = [], [1] * n, [1] * n for i in range(n): while s and s[-1][0] > A[i]: left[i] += s.pop()[1] s.append((A[i], left[i])) s = [] for i in range(n - 1, -1, -1): while s and s[-1][0] >= A[i]: right[i] += s.pop()[1] s.append((A[i], right[i])) ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod return ans |
Python3 V2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Author: Huahua, 366 ms class Solution: def sumSubarrayMins(self, A): kMod = 10 ** 9 + 7 n = len(A) left, right = [1] * n, [1] * n def fillLength(counts, start, end, step): s = [] for i in range(start, end, step): num = A[i] if step > 0 else A[i] - 1 while s and s[-1][0] > num: counts[i] += s.pop()[1] s.append((A[i], counts[i])) fillLength(left, 0, n, 1) fillLength(right, n - 1, -1, -1) ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod return ans |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment