Find sum of minimums of all subarrays.
Input: arr=[3,1,2,4] → Output: 17
Input: arr=[11,81,94,43,3] → Output: 444
Monotonic stack: for each element, compute how many subarrays it is the minimum of.
- For each arr[i]: find left boundary (previous smaller) and right boundary (next smaller or equal)
- Contribution = arr[i] * left_count * right_count
- Sum all contributions modulo 1e9+7
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> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
left[i] = st.isEmpty() ? i + 1 : i - st.peek();
st.push(i);
}
st.clear();
for (int i = n-1; i >= 0; i--) {
while (!st.isEmpty() && arr[st.peek()] > arr[i]) st.pop();
right[i] = st.isEmpty() ? n - i : st.peek() - i;
st.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)