diff options
Diffstat (limited to 'sum_subarr_mins.py')
-rw-r--r-- | sum_subarr_mins.py | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/sum_subarr_mins.py b/sum_subarr_mins.py new file mode 100644 index 0000000..38aeb98 --- /dev/null +++ b/sum_subarr_mins.py @@ -0,0 +1,28 @@ +# 907. Sum of Subarray Minimums + +""" +given an array of integers 'arr', find the sum of 'min(b)', where 'b' ranges +over every contiguous subarray of 'arr'. since the answer may be large, +return the answer modulo 10^9+7 +""" + + +class Solution(object): + def sumSubarrayMins(self, arr): + stack = [] + ans = 0 + arr = [float("-inf")] + arr + [float("-inf")] + for i, num in enumerate(arr): + while stack and arr[stack[-1]] > num: + curr = stack.pop() + ans += arr[curr] * (i - curr) * (curr - stack[-1]) + stack.append(i) + return ans % (10**9 + 7) + + +if __name__ == "__main__": + obj = Solution() + print(obj.sumSubarrayMins([3, 1, 2, 4])) + # expect: 17 + print(obj.sumSubarrayMins([11, 81, 94, 43, 3])) + # expect: 444 |