blob: 0cca2e083ac2d7d0a7ef07b83b6a846550757447 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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()
|
