907

1 files changed, 45 insertions, 0 deletions

diff --git a/907/main.py b/907/main.py
new file mode 100755
index 0000000..0cca2e0
--- /dev/null
+++ b/907/main.py
@@ -0,0 +1,45 @@
+#!/usr/bin/env python
+import typing
+
+
+class Solution:
+    def sumSubarrayMins(self, arr: typing.List[int]) -> int:
+        n = len(arr)
+        left = [-1] * n
+        right = [n] * n
+        stack = []
+
+        for i, value in enumerate(arr):
+            while stack and arr[stack[-1]] >= value:
+                stack.pop()
+            if stack:
+                left[i] = stack[-1]
+            stack.append(i)
+
+        stack = []
+
+        for i in range(n - 1, -1, -1):
+            while stack and arr[stack[-1]] > arr[i]:
+                stack.pop()
+            if stack:
+                right[i] = stack[-1]
+            stack.append(i)
+
+        mod = 10**9 + 7
+
+        result = (
+            sum((i - left[i]) * (right[i] - i) * value for i, value in enumerate(arr))
+            % mod
+        )
+
+        return result
+
+
+def main():
+    solution = Solution()
+    print(solution.sumSubarrayMins([3, 1, 2, 4]))
+    print(solution.sumSubarrayMins([11, 81, 94, 43, 3]))
+
+
+if __name__ == "__main__":
+    main()