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.
1#include <vector>
2#include <stack>
3using namespace std;
4
5typedef long long ll;
6class Solution {
7public:
8 int sumSubarrayMins(vector<int>& arr) {
9 const ll MOD = 1e9 + 7;
10 int n = arr.size();
11 vector<int> left(n), right(n);
12 stack<int> s1, s2;
13
14 for (int i = 0; i < n; i++) {
15 while (!s1.empty() && arr[s1.top()] > arr[i]) s1.pop();
16 left[i] = (s1.empty()) ? (i + 1) : (i - s1.top());
17 s1.push(i);
18 }
19
20 for (int i = n - 1; i >= 0; i--) {
21 while (!s2.empty() && arr[s2.top()] >= arr[i]) s2.pop();
22 right[i] = (s2.empty()) ? (n - i) : (s2.top() - i);
23 s2.push(i);
24 }
25
26 ll result = 0;
27 for (int i = 0; i < n; i++) {
28 result = (result + (ll)arr[i] * left[i] * right[i]) % MOD;
29 }
30 return (int)result;
31 }
32};This C++ solution is a faithful translation of the concept. It calculates how each integer affects the total using its role in various subarrays by determining its influence using distances in both directions.
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.
1def
Through dynamic programming, this Python solution consolidates subarray results iteratively, using an array dp to track cumulative outcomes efficiently.