Sponsored
Sponsored
The monotonic stack approach leverages a stack data structure to efficiently determine the minimum element of every subarray. By maintaining indexes and utilizing their properties, we can efficiently compute the sum of all minimum values for the contiguous subarrays.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the use of auxiliary arrays and a stack.
1def sumSubarrayMins(arr):
2 MOD = 10**9 + 7
3 n = len(arr)
4 stack = []
5 result = 0
6
7 for i in range(n + 1):
8 while stack and (i == n or arr[stack[-1]] >= arr[i]):
9 cur_index = stack.pop()
10 cur_value = arr[cur_index]
11 left = cur_index - stack[-1] if stack else cur_index + 1
12 right = i - cur_index
13 result += cur_value * left * right
14 result %= MOD
15 stack.append(i)
16
17 return result
18This Python solution efficiently computes the result by leveraging the stack to find contributions of each element iteratively to the final sum as the minimum of subarrays.
A dynamic programming approach can also be adopted to tackle the given problem. This method involves calculating the contribution of each element to subarray minimums utilizing previously calculated results intelligently.
Time Complexity: O(n)
Space Complexity: O(n), arising from stack usage and dp.
1#include <vector>
#include <stack>
using namespace std;
typedef long long ll;
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int MOD = 1e9 + 7;
int n = arr.size();
vector<int> dp(n);
stack<int> s;
ll result = 0;
for (int i = 0; i < n; ++i) {
while (!s.empty() && arr[s.top()] >= arr[i]) s.pop();
int k = (s.empty()) ? i + 1 : i - s.top();
dp[i] = (arr[i] * k + (s.empty() ? 0 : dp[s.top()])) % MOD;
result = (result + dp[i]) % MOD;
s.push(i);
}
return (int)result;
}
};In this C++ solution, a stack maintains previously seen elements, easing computation of minimum contributions by referring to the dp derived from prior computed sections.