Find sum of minimums of all subarrays of arr.
Input: arr=[3,1,2,4] → Output: 17. Minimums: [3]=3,[1]=1,[2]=2,[4]=4,[3,1]=1,[1,2]=1,[2,4]=2,[3,1,2]=1,[1,2,4]=1,[3,1,2,4]=1. Sum=17.
Input: arr=[11,81,94,43,3] → Output: 444
Monotonic stack: for each element find how many subarrays it is the minimum of (left and right boundaries).
- For each arr[i] find left[i]: distance to previous smaller element
- Find right[i]: distance to next smaller or equal element
- Contribution of arr[i] = arr[i] * left[i] * right[i]
- Sum all contributions with MOD
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
long MOD = 1_000_000_007L, res = 0;
int[] left = new int[n], right = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
stack.clear();
for (int i = n-1; i >= 0; i--) {
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) stack.pop();
right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
stack.push(i);
}
for (int i = 0; i < n; i++) res = (res + (long)arr[i] * left[i] * right[i]) % MOD;
return (int) res;
}
- Time Complexity: O(n)
- Space Complexity: O(n)