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 <stdio.h>
2#define MOD 1000000007
3#define MAX 30000
4
5int sumSubarrayMins(int* arr, int arrSize) {
6 long res = 0;
7 int stack[MAX], top = -1;
8 int left[MAX], right[MAX];
9
10 for (int i = 0; i < arrSize; ++i) {
11 while (top != -1 && arr[stack[top]] > arr[i]) --top;
12 left[i] = (top == -1) ? i + 1 : i - stack[top];
13 stack[++top] = i;
14 }
15
16 top = -1;
17 for (int i = arrSize - 1; i >= 0; --i) {
18 while (top != -1 && arr[stack[top]] >= arr[i]) --top;
19 right[i] = (top == -1) ? arrSize - i : stack[top] - i;
20 stack[++top] = i;
21 }
22
23 for (int i = 0; i < arrSize; ++i) {
24 res = (res + (long)arr[i] * left[i] * right[i]) % MOD;
25 }
26
27 return (int)res;
28}This C solution employs a monotonically increasing stack to determine the number of elements affected by each element of the array on either side, thus calculating its contribution to the final sum.
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.
1const
This JavaScript dynamic programming method regards elements by opting for arrays, encompassing accumulative subarray submatrix calculations step by step.