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.
1import java.util.Stack;
2
3public class Solution {
4 public int sumSubarrayMins(int[] arr) {
5 long MOD = (long)1e9 + 7;
6 int n = arr.length;
7 Stack<Integer> stack = new Stack<>();
8 long sum = 0;
9
10 for (int i = 0; i <= n; i++) {
11 while (!stack.isEmpty() && (i == n || arr[stack.peek()] >= arr[i])) {
12 int index = stack.pop();
13 int curValue = arr[index];
14 int left = stack.isEmpty() ? index + 1 : index - stack.peek();
15 int right = i - index;
16 sum += (long)curValue * left * right;
17 sum %= MOD;
18 }
19 stack.push(i);
20 }
21
22 return (int)sum;
23 }
24}This Java implementation utilizes a monotonic stack pattern similarly, processing elements from the left to the right to compute how many times each element serves as a minimum in contiguous 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#
This C solution uses an array dp to compute subarray minimum sums progressively, allowing each integer's effect to persist cumulatively across numerous subarray possibilities.