Sponsored
Sponsored
This approach leverages a monotonic stack to determine the contribution of each element when it is the minimum in its subarrays. Using this, we can efficiently calculate the total subarray strength including this minimum. Along with this, prefix sums help in computing the sum of elements in a range efficiently.
Time Complexity: O(n), where n is the length of the strength array. Space Complexity: O(n) due to the prefix sums and stack usage.
1def totalStrength(strength):
2 MOD = 10**9 + 7
3 n = len(strength)
4
5 # Compute prefix sums
6 prefix = [0] * (n + 1)
7 for i in range(n):
8 prefix[i + 1] = (prefix[i] + strength[i]) % MOD
9
10 # Use stack to find previous and next smaller
11 prev_smaller = [-1] * n
12 next_smaller = [n] * n
13 stack = []
14
15 for i in range(n):
16 while stack and strength[stack[-1]] > strength[i]:
17 next_smaller[stack.pop()] = i
18 stack.append(i)
19
20 stack = []
21 for i in reversed(range(n)):
22 while stack and strength[stack[-1]] >= strength[i]:
23 prev_smaller[stack.pop()] = i
24 stack.append(i)
25
26 result = 0
27 for i in range(n):
28 # Index i the minimum in its range
29 l, r = prev_smaller[i], next_smaller[i]
30 left_part = (prefix[i] - (prefix[l + 1] if l >= 0 else 0)) % MOD
31 right_part = (prefix[r] - (prefix[i + 1] if i + 1 < n else 0)) % MOD
32 pos_count = (i - l) * (r - i) % MOD
33 result = (result + strength[i] * (pos_count * left_part - right_part) % MOD) % MOD
34
35 return result
36
37# Example usage:
38print(totalStrength([1,3,1,2])) # Output: 44In this solution, we calculate the prefix sums for the strength array to efficiently get subarray sums. The monotonic stack helps track the previous and next smaller element positions for each element. We calculate each element's contribution to the total strength by considering it as the minimal value for contiguous subarrays and using the previously calculated ranges and prefix sums.
This approach directly calculates each subarray's total strength using nested loops with some optimizations to reduce redundant calculations, like avoiding repeated strength sums by leveraging previous computations.
Time Complexity: O(n), since each element is pushed and popped from the stack once. Space Complexity: O(n), due to the prefix arrays and auxiliary space used for indices.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int TotalStrength(int[] strength) {
const int MOD = 1000000007;
int n = strength.Length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++)
prefix[i + 1] = (prefix[i] + strength[i]) % MOD;
int[] prevSmaller = new int[n];
int[] nextSmaller = new int[n];
Array.Fill(prevSmaller, -1);
Array.Fill(nextSmaller, n);
var stack = new Stack<int>();
for (int i = 0; i < n; i++) {
while (stack.Count > 0 && strength[stack.Peek()] > strength[i]) {
nextSmaller[stack.Pop()] = i;
}
stack.Push(i);
}
stack.Clear();
for (int i = n - 1; i >= 0; i--) {
while (stack.Count > 0 && strength[stack.Peek()] >= strength[i]) {
prevSmaller[stack.Pop()] = i;
}
stack.Push(i);
}
long totalStrength = 0;
for (int i = 0; i < n; i++) {
int l = prevSmaller[i], r = nextSmaller[i];
long leftPart = (prefix[i] - (l >= 0 ? prefix[l + 1] : 0) + MOD) % MOD;
long rightPart = (prefix[r] - (i + 1 < n ? prefix[i + 1] : 0) + MOD) % MOD;
long posCount = ((long)(i - l) * (r - i)) % MOD;
totalStrength = (totalStrength + strength[i] * (posCount * leftPart - rightPart + MOD) % MOD) % MOD;
}
return (int)totalStrength;
}
}
// Example usage:
// Solution sol = new Solution();
// Console.WriteLine(sol.TotalStrength(new int[]{1,3,1,2})); // Output: 44The C# implementation is akin to the C++ one, employing stacks to track previous and next smaller elements and compute the total strength of subarrays by iterating over the array elements. Index arrays 'prevSmaller' and 'nextSmaller' mirror the boundaries while computing contiguous elements where current is the minimum.